Sliding Window — Count Number of Nice Subarrays
↗ LeetCode: Count Number of Nice Subarrays · Medium · pattern chapter →
Given an array nums and integer k, return the number of contiguous subarrays containing exactly k odd numbers.
Example 1 — nums = [1,1,2,1,1], k = 3 → 2Example 2 — nums = [2,4,6], k = 1 → 0Example 3 — nums = [2,2,2,1,2,2,1,2,2,2], k = 2 → 16
Constraints — 1 ≤ n ≤ 5 · 10⁴; 1 ≤ nums[i] ≤ 10⁵; 1 ≤ k ≤ n. Brute checks every subarray in O(n²) = 2.5·10⁹ ops at n=5·10⁴ (TLE). Sliding-window atMost(k) − atMost(k−1) is O(n) = 5·10⁴ ops.
⏱️Interview timer00:00
Approach 1 — Every subarray
Intuition. For each [i, j], count odd numbers.
int numberOfSubarraysBrute(int[] nums, int k) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
int odd = 0;
for (int j = i; j < n; j++) {
if (nums[j] % 2 == 1) odd++;
if (odd == k) count++;
else if (odd > k) break;
}
}
return count;
}2
3
4
5
6
7
8
9
10
11
12
Complexity — Time O(n²); Space O(1).
Approach 2 — Reduce to Binary Subarrays With Sum
Insight from brute. Map odd → 1, even → 0. Now the problem is: count subarrays with sum exactly k on a binary array — which is exactly Binary Subarrays With Sum. Use the atMost trick.
int numberOfSubarrays(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
int atMost(int[] nums, int k) {
if (k < 0) return 0;
int left = 0, odd = 0, res = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] % 2 == 1) odd++;
while (odd > k) if (nums[left++] % 2 == 1) odd--;
res += right - left + 1;
}
return res;
}2
3
4
5
6
7
8
9
10
11
12
13
Then atMost(3) - atMost(2) = 14 - 12 = 2.
Complexity — Time O(n); Space O(1).
Approach 3 — Count-of-prefix-sums with prefix map (O(n) space)
Insight. Prefix-count of odd numbers up to index i. Subarray [i+1, j] has k odd iff oddPref[j+1] - oddPref[i] = k. Same hash-map trick as Subarray Sum Equals K.
int numberOfSubarraysPS(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int odd = 0, res = 0;
for (int x : nums) {
odd += x & 1;
res += cnt.getOrDefault(odd - k, 0);
cnt.merge(odd, 1, Integer::sum);
}
return res;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every subarray | O(n²) | O(1) | baseline |
Two atMost windows | O(n) | O(1) | optimum |
| Prefix hash map | O(n) | O(n) | acceptable — same as SSEqK |
When to use which
- "Exactly k of X" over non-negative counts →
atMosttrick. - Arbitrary values (negatives, etc.) → prefix + hash map (works for any).
- "At most k" → single sliding window.
- "Return the subarrays" → prefix + indices; loses O(1) space.
Related problems
- Binary Subarrays With Sum — identical mechanics
- Subarrays with K Different Integers — same atMost pattern for distinct count
- Subarray Sum Equals K — hash-map sibling