Count Number of Nice Subarrays
Problem Statement
Given an integer array nums and an integer k, return the number of contiguous subarrays that contain exactly k odd numbers. Such subarrays are called nice subarrays.
Input
An integer array nums and an integer k, the exact number of odd values required in each valid subarray.
Output
An integer: the number of contiguous subarrays containing exactly k odd numbers.
Constraints
- •
1 <= nums.length <= 5 * 10^4 - •
1 <= nums[i] <= 10^5 - •
1 <= k <= nums.length
Examples
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
16Learning Objectives
- Map parity to a binary signal where odd values behave like **1** and even values behave like **0**.
- Reuse **exactly(K) = atMost(K) - atMost(K - 1)** for exact odd-count subarrays.
- Maintain a window with at most **k** odd values using two pointers.
- Connect this problem directly to Binary Subarrays With Sum.
Intuition
Pattern Identification
Ignore the actual magnitudes. The problem only cares whether each number is odd. That means the array can be viewed as a binary sequence: odd maps to 1, even maps to 0. Now the task is to count subarrays with binary sum exactly k.
As in the previous problem, exact counts are easier through the at-most difference. A window with at most k odd values is monotone under removing elements from the left. Therefore exactly(K) = atMost(K) - atMost(K - 1) counts exactly the nice subarrays without enumerating every start and end.
Common mistakes
- ×Using the numeric sum of the array instead of counting odd values only.
- ×Trying to reset the window at even numbers, even though evens can be part of many nice subarrays.
- ×Forgetting that every valid at-most window ending at **right** contributes **right - left + 1** suffixes.
- ×Handling **k - 1** without a negative guard in a reusable helper.
Algorithm Explanation
Window setup
Build atMost(limit) where the window state is oddCount, not a sum of values. When nums[right] is odd, increment oddCount. While oddCount > limit, move left forward and decrement oddCount whenever an odd value leaves.
Window visualization
For nums = [1,1,2,1,1] and limit = 3, when right = 3, the window [1,1,2,1] has exactly three odds and adds 4 valid suffixes. When right = 4 adds another odd, the window has four odds, so left moves past the first odd. The valid window becomes [1,2,1,1] and adds 4 suffixes for the at-most count.
Algorithm
- Treat each odd number as contributing 1 to oddCount and each even number as contributing 0.
- In atMost(limit), return 0 if limit < 0.
- Expand right and update oddCount when the entering number is odd.
- While oddCount > limit, remove nums[left] from the parity count and advance left.
- Add right - left + 1 to count all valid suffixes ending at right.
- Return atMost(k) - atMost(k - 1).
Solutions
Solution: At-most difference on odd count
This is Binary Subarrays With Sum after a parity transformation. The helper never needs to build a separate binary array; it counts odd values directly while maintaining the at-most invariant.
Step-by-step
- Call atMost(nums, k) to count subarrays with at most k odd numbers.
- Call atMost(nums, k - 1) to count subarrays with too few odd numbers.
- During each pass, increment oddCount when the right value is odd.
- Shrink from the left until oddCount is within the limit.
- Add right - left + 1 for each right edge and subtract the two pass totals.
O(n)
O(1)
Two linear passes with only pointers and an odd counter.
Java implementation
Dry Run
Sample input
nums = [1,1,2,1,1], k = 3. Count atMost(3) and atMost(2) by tracking only odd values.
| phase | right | value parity | left after shrink | odd count | subarrays added | running count | meaning |
|---|---|---|---|---|---|---|---|
| atMost(3) | 0 | odd | 0 | 1 | 1 | 1 | one odd is within limit |
| atMost(3) | 1 | odd | 0 | 2 | 2 | 3 | two odds are within limit |
| atMost(3) | 2 | even | 0 | 2 | 3 | 6 | even extends all suffixes |
| atMost(3) | 3 | odd | 0 | 3 | 4 | 10 | limit reached |
| atMost(3) | 4 | odd | 1 | 3 | 4 | 14 | shrink past the first odd |
| atMost(2) | 0 | odd | 0 | 1 | 1 | 1 | one odd allowed |
| atMost(2) | 1 | odd | 0 | 2 | 2 | 3 | limit reached |
| atMost(2) | 2 | even | 0 | 2 | 3 | 6 | even does not change odd count |
| atMost(2) | 3 | odd | 1 | 2 | 3 | 9 | remove the first odd |
| atMost(2) | 4 | odd | 2 | 2 | 3 | 12 | remove the second odd |
The helper counts are atMost(3) = 14 and atMost(2) = 12. The difference is 2, matching the two nice subarrays.
Interview Tips
State the transformation first: odd numbers are ones, even numbers are zeros. Then the problem becomes exact binary sum, so the same atMost(K) - atMost(K - 1) reasoning applies. This framing is stronger than presenting it as a brand-new trick and helps you generalize to other categorical-count windows.
Likely follow-ups
- How would you solve this with prefix counts of odd numbers instead of sliding window?
- How would you count subarrays with exactly **k** even numbers?
- How would the solution change if the condition were exactly **k** values divisible by **3**?
- How can you compute the answer by multiplying choices around the positions of odd values?
Similar Problems
Key Takeaways
- Parity problems often reduce to binary-array problems.
- Nice subarrays are subarrays with binary odd-count sum exactly **k**.
- The at-most helper can count odd values directly without materializing a transformed array.
- Even numbers are not separators; they multiply the number of valid starts and ends.