Count Number of Nice Subarrays
Count Number of Nice Subarrays: return the number of subarrays containing exactly k odd numbers.
- 1 <= nums.length <= 50000
- 1 <= nums[i] <= 10^5
- 1 <= k <= nums.length
Intuition
Count number of nice subarrays counts subarrays containing exactly k odd numbers. The reframing that makes this easy is to notice that the actual values are irrelevant — only parity matters:
- Replace each number with 1 if odd and 0 if even, and the problem becomes counting subarrays with sum exactly k.
That is Subarray Sum Equals K, and both of its standard solutions apply unchanged.
The prefix sum with a hash map approach tracks how many odd numbers have been seen so far. A subarray ending at index i contains exactly k odds when some earlier prefix had count − k odds. Seed the map with {0: 1} so subarrays starting at index 0 are counted — omitting that seed is the standard bug in every problem of this family.
The sliding window approach works because the transformed values are non-negative, so the running count never decreases. But a window with exactly k odds cannot be counted directly: even numbers on either side extend the window without changing the count, so many windows share the same odd count.
The fix is the same identity used in Binary Subarrays with Sum:
exactly(k) = atMost(k) − atMost(k − 1)
Counting at most k odds slides cleanly, and the subtraction isolates the exact count. Recognising that these two problems are the same one under a transformation makes both routine.
"Exactly k odd numbers" solved as atMost(k) - atMost(k-1). A window can't test for exactly-k because the condition isn't monotone, but at-most is — the same decomposition as Binary Subarrays With Sum, with parity in place of value.
Approach
Before reading on: price up what the direct approach costs here, then ask what running total makes each query a single subtraction. Aim for O(n) time and O(1) space.
Reduce to parity
Replace each number with 1 if odd and 0 if even. The actual values never matter — this turns the problem into counting subarrays with sum exactly k.
Recognise the known problem
This is now Subarray Sum Equals K on a binary array. Both of that problem's standard solutions transfer without modification.
Track prefix counts in a map
A subarray ending at i has exactly k odds when an earlier prefix had count - k. Record how many times each running count has occurred and add the matching tally.
Seed the map with zero
Initialise with {0: 1}. Without it every subarray starting at index 0 is missed — the standard bug across this entire family of problems.
Consider the sliding-window alternative
Transformed values are non-negative, so the running count never decreases and windowing is valid. But even numbers at either end make many windows share one odd count.
Subtract to isolate the exact count
exactly(k) = atMost(k) - atMost(k - 1). Counting at most k slides cleanly where counting exactly k does not — the same identity as Binary Subarrays with Sum.
Cost of the approach
One pass either way gives O(n) time. The hash map uses O(n) space; the sliding window uses O(1).
Solution & live demo
Common pitfalls
Removing the wrong element when shrinking
odd -= nums[left] & 1 left += 1
left += 1 odd -= nums[left - 1] & 1
Both orderings can be written correctly, but they must agree — increment then subtract nums[left-1], or subtract nums[left] then increment. Mixing them skips an element and leaves the counter out of step with the window.
Omitting the negative guard
def atMost(m):
left = odd = total = 0if m < 0:
return 0For k = 0 the second call receives −1, and the shrink loop then runs past the right edge producing a negative count. No subarray contains at most −1 odd numbers, so 0 is correct.
Testing oddness with % 2 == 1
odd += 1 if v % 2 == 1 else 0
odd += v & 1
Equivalent for positive values here, but % on negatives returns −1 in C++ and Java, so the test silently fails. & 1 is correct for every sign and faster.
Edge cases
atMost(-1) must return 0; the answer counts subarrays with no odd numbers at all.
Both terms are equal and the difference is 0.
Only k = 0 yields a non-zero answer.
The window shrinks constantly and the count is n - k + 1.