Count Number of Nice Subarrays
Description
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers in the array, so no nice subarrays exist.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
Explanation: The two odd numbers are at indices 3 and 6. We can extend left from index 3 (3 choices: start at 0,1,2,3) and right from index 6 (4 choices: end at 6,7,8,9). Total = 4 * 4 = 16 nice subarrays.
Constraints
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Sliding window or prefix sum with hash map
- Approach
- Count subarrays where prefix[j] - prefix[i] = k using a hash map
- Complexity
- Transform odd/even to 1/0, then use prefix sum technique
Notes
Show Notes
Count Number of Nice Subarrays
Approach: Prefix Sum with Hash Map
Key Insight
Transform the problem: Replace each number with 1 (odd) or 0 (even), then we’re looking for subarrays with sum = k.
nums: [2, 2, 1, 2, 2]
transformed: [0, 0, 1, 0, 0]
Prefix Sum
prefix[i] = count of odd numbers from index 0 to i-1.
index: -1 0 1 2 3 4
prefix: 0 0 0 1 1 1
↑ ↑ ↑ ↑ ↑
after processing each element
The Trick
A subarray from index i to j has exactly k odd numbers if:
prefix[j+1] - prefix[i] = k
Rearranging: we need prefix[i] = prefix[j+1] - k
So at each position, we ask: “How many earlier prefix values equal current_prefix - k?”
Trace Through Example
nums = [2, 2, 1, 2, 2], k = 1
| Step | num | curr (prefix) | Looking for curr-k | Map has it? | result | Map after |
|---|---|---|---|---|---|---|
| init | - | - | - | - | 0 | {0: 1} |
| 0 | 2 (even) | 0 | 0-1 = -1 | No | 0 | {0: 2} |
| 1 | 2 (even) | 0 | 0-1 = -1 | No | 0 | {0: 3} |
| 2 | 1 (odd) | 1 | 1-1 = 0 | Yes! count=3 | 0+3=3 | {0: 3, 1: 1} |
| 3 | 2 (even) | 1 | 1-1 = 0 | Yes! count=3 | 3+3=6 | {0: 3, 1: 2} |
| 4 | 2 (even) | 1 | 1-1 = 0 | Yes! count=3 | 6+3=9 | {0: 3, 1: 3} |
Final answer: 9 ✓
Why Does This Work?
At index 2 (the 1), curr = 1. We look for prefix = 0 in our map. We have 3 positions where prefix was 0 (before index 0, 1, and 2). Each of those is a valid starting point for a subarray ending at index 2 with exactly 1 odd number:
- Start before index 0 →
[2,2,1] - Start before index 1 →
[2,1] - Start before index 2 →
[1]
At index 3 and 4, we still have curr = 1, and those same 3 starting points still work, giving us 3 more subarrays each time.
Solution
def solution(nums: list[int], k: int) -> int:
prefix_count = {0: 1} # "prefix 0" exists once (before array starts)
curr = 0
result = 0
for num in nums:
if num % 2 != 0:
curr += 1
# How many subarrays ending here have exactly k odds?
result += prefix_count.get(curr - k, 0)
# Record this prefix value
prefix_count[curr] = prefix_count.get(curr, 0) + 1
return result
Complexity
- Time: O(n) - single pass through the array
- Space: O(n) - hash map stores at most n+1 distinct prefix values
Solutions
Show PY Solution
def solution(nums: list[int], k: int) -> int:
m = {0: 1}
curr = 0
count = 0
for i in range(len(nums)):
curr += nums[i] % 2
if curr - k in m:
count += m[curr - k]
if curr not in m:
m[curr] = 0
m[curr] += 1
return count