#1248
Count Number of Nice Subarrays
Medium atMost(k) − atMost(k−1)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count subarrays that contain exactly k odd numbers.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count subarrays with exactly k odd numbers.
Why this works: counting "at most k" is easy with a window (each right end adds window-length subarrays). Exactly k = atMost(k) - atMost(k-1).
Example: [1, 1, 2, 1, 1], k = 3
atMost(3) = 14, atMost(2) = 12answer 2: [1,1,2,1] and [1,2,1,1]
✦Hints open one at a time
"Exactly k" is hard to slide directly. "At most k" is easy.
exactly(k) = atMost(k) − atMost(k − 1).
↗Approach
atMost(k) counts subarrays with at most k odd numbers: expand right, shrink while odds > k, and add the window length (every subarray ending at r and starting in the window qualifies). Subtract the two results.
</>Solution (Java)
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
int left = 0, odds = 0, count = 0;
for (int r = 0; r < nums.length; r++) {
if (nums[r] % 2 == 1) odds++;
while (odds > k) {
if (nums[left] % 2 == 1) odds--;
left++;
}
count += r - left + 1; // subarrays ending at r
}
return count;
}
}!Common mistake
Adding 1 per valid window instead of the window length — you'd count only one subarray per right end.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon