Count Number of Nice Subarrays
mediumTime: O(n)Space: O(1)
Signals to notice
count subarrays with exactly k odd numbersexact = atMost(k) - atMost(k-1)same trick as subarrays with k different integers
Brute force first
Check every subarray — O(n²).
The key insight
exactly(k) = atMost(k) - atMost(k-1). atMost(k): sliding window counting subarrays with ≤ k odd numbers. O(n).
What must stay true
Replace 'odd' with a counter. atMost(k) counts subarrays with ≤ k odds using the standard window technique. Subtraction gives exactly k.
Easy way to go wrong
Same as Subarrays with K Different Integers — direct 'exactly k' counting is hard, but the subtraction trick makes it easy.