Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
Example 1:
Input: nums = [1,1,2,1,1], k = 3 Output: 2 Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:
Input: nums = [2,4,6], k = 1 Output: 0 Explanation: There are no odd numbers in the array.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 Output: 16
Constraints:
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.lengthThe key idea in #1248 Count Number of Nice Subarrays is to count subarrays that contain exactly k odd numbers. A helpful transformation is to treat every number as either odd (1) or even (0), turning the problem into counting subarrays with a sum equal to k.
One efficient method uses a prefix sum with a hash map. As you traverse the array, maintain the cumulative count of odd numbers. For each position, check how many times a prefix with value currentOddCount - k has appeared before. This allows you to count valid subarrays ending at the current index in constant time.
Another elegant approach uses the sliding window technique with the "at most k" trick. By counting subarrays with at most k odd numbers and subtracting those with at most k-1, you obtain the number with exactly k. Both approaches run in linear time, making them efficient for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Hash Map | O(n) | O(n) |
| Sliding Window (At Most K Trick) | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
After replacing each even by zero and every odd by one can we use prefix sum to find answer ?
Can we use two pointers to count number of sub-arrays ?
Can we store the indices of odd numbers and for each k indices count the number of sub-arrays that contains them ?
The main idea is to use a sliding window to keep track of the current subarray and count of odd numbers. If the count of odd numbers becomes more than k, move the start pointer to decrease the count. For every suitable subarray, calculate the number of possible subarrays that end at the current end pointer. This way, we can efficiently count the nice subarrays.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) for the dictionary to store prefix counts.
1#include <unordered_map>
2using namespace std;
3
4class Solution {
5public:
6 int numberOfSubarrays(vector<int>& nums, int k) {
7 int result = 0, oddCount = 0;
8 unordered_map<int, int> prefixCount;
9 prefixCount[0] = 1;
10
11 for (int num : nums) {
12 if (num % 2 == 1) {
13 oddCount++;
14 }
15 if (prefixCount.find(oddCount - k) != prefixCount.end()) {
16 result += prefixCount[oddCount - k];
17 }
18 prefixCount[oddCount]++;
19 }
20
21 return result;
22 }
23};This C++ solution mirrors the Python solution by using an unordered_map to manage prefix counts of odd numbers. With this map, we can efficiently determine the count of nice subarrays as we iterate through the nums array.
This approach involves checking every possible subarray of nums and counting the odd numbers in each. If a subarray contains exactly k odd numbers, it is counted as nice. While straightforward to implement, this method is not efficient for large arrays as its time complexity is quadratic.
Time Complexity: O(n^2), where n is the length of nums.
Space Complexity: O(1)
1def number_of_subarraysWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a common interview-style question because it combines prefix sums, sliding windows, and counting techniques. Variations of this pattern often appear in FAANG and other technical interviews.
Yes, the sliding window method works well by counting subarrays with at most k odd numbers and subtracting those with at most k-1. This trick converts the exact-count requirement into two easier window calculations.
A hash map is commonly used with the prefix sum approach to store frequencies of odd-count prefixes. This helps quickly determine how many previous subarrays can form a valid result with the current position.
The optimal approaches are Prefix Sum with a Hash Map and the Sliding Window 'at most k' technique. Both methods scan the array once and count valid subarrays efficiently in O(n) time.
This Python solution iterates over all possible subarrays starting from each index. For each subarray, it counts the number of odd numbers and checks if this matches k. If matched, the count of nice subarrays is incremented.