Problem Explanation

Given an array of integers called nums and an integer k, we are tasked with finding all subarrays that have exactly k odd numbers. A subarray is a contiguous part of an array. Our job is to return the count of such "nice" subarrays.

Let's take an example to illustrate this:

Consider nums = [1, 2, 1, 1, 2] and k = 2. Here, the subarrays that have exactly 2 odd numbers are: [1, 2, 1], [1, 2, 1, 1], [2, 1, 1], [1, 1, 2]. Hence, the output will be 4.

Approach

The solution uses a sliding window technique coupled with counting the number of sub-arrays with k odd numbers or fewer.

The main idea is that the number of sub-arrays with exactly k odd numbers is the difference between the number of sub-arrays with k odd numbers or fewer and the number of sub-arrays with k - 1 odd numbers or fewer.

Python

1
2python
3class Solution:
4    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
5        return self.atMost(nums, k) - self.atMost(nums, k - 1)
6   
7    def atMost(self, nums: List[int], k: int) -> int:
8        count = 0
9        left = 0
10        for right in range(len(nums)):
11            if nums[right] % 2 == 1:
12                k -= 1
13            while k < 0:
14                if nums[left] % 2 == 1:
15                    k += 1
16                left += 1
17            count += right - left + 1
18        return count

Java

1
2java
3class Solution {
4    public int numberOfSubarrays(int[] nums, int k) {
5        return atMost(nums, k) - atMost(nums, k - 1);
6    }
7    
8    private int atMost(int[] nums, int k) {
9        int count = 0;
10        int left = 0;
11        for (int right = 0; right < nums.length; ++right) {
12            if (nums[right] % 2 == 1) {
13                --k;
14            }
15            while (k < 0) {
16                if (nums[left] % 2 == 1) {
17                    ++k;
18                }
19                ++left;
20            }
21            count += right - left + 1;
22        }
23        return count;
24    }
25}

JavaScript

1
2javascript
3class Solution {
4    numberOfSubarrays(nums, k) {
5        return this.atMost(nums, k) - this.atMost(nums, k - 1);
6    }
7    
8    atMost(nums, k) {
9        let count = 0;
10        let left = 0;
11        for (let right = 0; right < nums.length; ++right) {
12            if (nums[right] % 2 == 1) {
13                --k;
14            }
15            while (k < 0) {
16                if (nums[left] % 2 == 1) {
17                    ++k;
18                }
19                ++left;
20            }
21            count += right - left + 1;
22        }
23        return count;
24    }
25}

C++

1
2cpp
3class Solution {
4public:
5    int numberOfSubarrays(vector<int>& nums, int k) {
6        return atMost(nums, k) - atMost(nums, k - 1);
7    }
8    
9private:
10    int atMost(vector<int>& nums, int k) {
11        int count = 0;
12        int left = 0;
13        for (int right = 0; right < nums.size(); ++right) {
14            if (nums[right] & 1) {
15                --k;
16            }
17            while (k < 0) {
18                if (nums[left] & 1) {
19                    ++k;
20                }
21                ++left;
22            }
23            count += right - left + 1;
24        }
25        return count;
26    }
27};

C#

1
2csharp
3public class Solution {
4    public int NumberOfSubarrays(int[] nums, int k) {
5        return AtMost(nums, k) - AtMost(nums, k - 1);
6    }
7    
8    private int AtMost(int[] nums, int k) {
9        int count = 0;
10        int left = 0;
11        for (int right = 0; right < nums.Length; ++right) {
12            if (nums[right] % 2 == 1) {
13                --k;
14            }
15            while (k < 0) {
16                if (nums[left] % 2 == 1) {
17                    ++k;
18                }
19                ++left;
20            }
21            count += right - left + 1;
22        }
23        return count;
24    }
25}

We perform these operations for all n elements in the array, thus the time complexity approximately is O(n).# Conclusion

The problem of finding subarrays that contain exactly k odd numbers can be solved using a sliding window algorithm. This technique offers an efficient solution in terms of time complexity(O(n)) as well as space complexity(O(1)). It is worth noting that this approach is scalable, meaning it can be applied to larger data sets with little modification.

This relative efficiency and scalability make it a suitable algorithm to employ in dealing with data manipulation problems, such as this, especially when working with large data sets often encountered in the real world scenarios.

We have implemented our solution using multiple programming languages (Python, Java, JavaScript, C++, and C#). Each one of these languages follows the same logic but utilises its language-specific syntax.

Understanding the sliding window technique and its application is a fundamental requirement for anyone who wants to excel in coding interviews. The ability to apply this technique, amongst others, to problems can often be the difference between an average and exceptional performance in such scenarios.

In conclusion, the journey to becoming proficient at data manipulation tasks and array-based challenges begins with understanding the fundamentals of subarray problems, their underlying algorithms and techniques such as the sliding window.