Count Number of Nice Subarrays
mediumTime: O(n)Space: O(1)
Recognize the pattern
count subarrays with exactly k odd numbersexact = atMost(k) - atMost(k-1)same trick as subarrays with k different integers
Brute force idea
Check every subarray — O(n²).
Better approach
exactly(k) = atMost(k) - atMost(k-1). atMost(k): sliding window counting subarrays with ≤ k odd numbers. O(n).
Key invariant
Replace 'odd' with a counter. atMost(k) counts subarrays with ≤ k odds using the standard window technique. Subtraction gives exactly k.
Watch out for
Same as Subarrays with K Different Integers — direct 'exactly k' counting is hard, but the subtraction trick makes it easy.