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.
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
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.