Count Number of Nice Subarrays

1. The "Exactly K" = "At Most K" minus "At Most K-1" Trick

• Counting subarrays with exactly K odd numbers directly is tricky with a sliding window.
• Instead, we compute: atMost(k) - atMost(k - 1).
• atMost(k) counts all subarrays with 0, 1, 2, ..., or k odd numbers.
• Subtracting atMost(k - 1) removes those with fewer than k odds, leaving exactly k.

2. The atMost Helper

• Initialize left = 0, odds = 0 (count of odd numbers in window), and count = 0.
• Iterate right across the array. If nums[right] is odd, increment odds.

3. Shrink When Too Many Odds

• While odds > goal, check if nums[left] is odd (if so, decrement odds), then increment left.
• This contracts the window until we have at most goal odd numbers.

4. Count Valid Subarrays

• After adjusting, every subarray ending at right and starting from any index in [left, right] has at most goal odd numbers.
• Add right - left + 1 to count.

5. Combine the Results

• Return atMost(k) - atMost(k - 1) to get the count of subarrays with exactly k odd numbers.

🧠 Key Insight

The atMost subtraction pattern converts an "exactly K" problem into two simpler "at most K" problems, each solvable with a standard sliding window. This runs in O(n) time (two passes) and O(1) space. The key observation is that exactly(k) = atMost(k) - atMost(k-1) because the set of subarrays with at most k odds includes all subarrays with at most k-1 odds as a subset.