Count Number of Nice Subarrays
Return the number of subarrays containing exactly k odd numbers.
Open on LeetCode ↗Intuition
The trap is trying to slide a window directly on "exactly k odd numbers." Exactly-k is not monotone: adding an element can jump you from valid to invalid with no shrink that fixes it, so there is no correct rule for when to move left. At-most-k, by contrast, is monotone — shrinking a window can only help — so compute atMost(k) - atMost(k-1). Every subarray with at most k odds, minus every subarray with at most k-1, leaves exactly those with precisely k. Two easy passes replace one hard one.
"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
Reduce the array to parity
Only oddness matters, so treat the array as binary: odd is 1, even is 0. The question becomes counting subarrays whose sum is exactly k, which makes the structure obvious.
Write atMost(k)
A standard window: grow right, add the parity, and while the running count exceeds k, shrink from the left. After each step, add right - left + 1 to the total — that is the number of subarrays ending at right that are legal, since every start from left to right works.
Subtract to get exactly
exactly(k) = atMost(k) - atMost(k-1). Each pass is O(n), so the whole thing is O(n) with O(1) space. Guard atMost for a negative k by returning 0, which matters when k is 0. The same pattern solves Subarrays with K Different Integers, and it is worth learning as a template rather than a one-off.
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.