Count Number of Nice Subarrays
Count the contiguous subarrays that contain exactly k odd numbers, as subarrays with at most k odds minus those with at most k - 1, each a sliding window.
Problem Understanding
Count Number of Nice Subarrays: a contiguous subarray is nice if it contains exactly k odd numbers. Given nums and k, return the number of nice subarrays.
Examples: [1,1,2,1,1], k 3 → 2; [2,4,6], k 1 → 0; [2,2,2,1,2,2,1,2,2,2], k 2 → 16.
The Intuition: Only Parity Matters
Odd numbers count, even numbers are filler. That makes this Binary Subarrays With Sum in disguise:
- atMost(g): a sliding window that shrinks while it holds more than g odds and adds
right − left + 1each step. - Exactly k = atMost(k) − atMost(k − 1).
The prefix-count alternative is the same idea as Subarray Sum Equals K.
Interactive Walkthrough
k = 3 · BOLD = ODD · atMost(3) − atMost(2)
EXACTLY = AT MOST − AT MOST
pass 1: at most 3 odd
0
1
2
3
4
odds
:
count
:
answer
:
Exactly 3 odd numbers = (at most 3) − (at most 2)
Next
atMost(3): count subarrays with at most 3 odd numbers
nums
k
Odd numbers are bold. Two passes run, at most k and at most k − 1; on each count step the shaded cells are the starting points counted. Try Example 3 to see evens multiply the count.
Dry Run Table
Input: [1,1,2,1,1], k = 3.
| Pass | Counts per right | Total |
|---|---|---|
| atMost(3) | 1, 2, 3, 4, 4 | 14 |
| atMost(2) | 1, 2, 3, 3, 3 | 12 |
Answer: 14 − 12 = 2 ([1,1,2,1] and [1,2,1,1]).
The Solution Template
The Binary Subarrays With Sum helper, counting odd numbers.
Count Number of Nice Subarrays Code
1var numberOfSubarrays = function(nums, k) {2 const atMost = (g) => {3 if (g < 0) return 0;4 let left = 0, odds = 0, count = 0;5 for (let right = 0; right < nums.length; right++) {6 odds += nums[right] & 1;7 while (odds > g) odds -= nums[left++] & 1;8 count += right - left + 1;9 }10 return count;11 };12 return atMost(k) - atMost(k - 1);13};
Edge Cases & Common Mistakes
- No odd numbers: both passes count everything; the answer is 0.
- k larger than the number of odds: the answer is 0.
- Counting only when odds == k: misses windows that differ by evens at the ends.
- Forgetting the g < 0 guard: only matters if k could be 0; LeetCode has k ≥ 1, but the helper stays correct with it.
- Long runs of evens: they are why the count can be large; use the subtraction, not enumeration.
Summary
Treat odd as 1 and even as 0, count windows with at most k odds with a shrinking window, and return atMost(k) − atMost(k − 1). O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet