Problem Breakdown
We need to count the number of continuous subarrays that contain exactly k odd integers. Even numbers are treated as neutral (value 0) in terms of counting, but they define the boundaries and length of valid windows.
Given the constraint , an solution iterating through all subarrays will exceed time limits. We must achieve efficiency.
Key Constraints & Edge Cases:
- Exact Match: The requirement is exactly
kodds, not “at least”. This distinguishes it from standard sliding window problems which often handle ranges of sums. - No Odds: If the array has fewer than
kodd numbers total, the answer must be 0. - Initialization: We need to account for subarrays starting at index 0 correctly by initializing our frequency map with a count of 1 for an initial prefix sum of 0 (representing zero odds seen before any elements).
Intuition
This problem is structurally equivalent to LeetCode Problem 967 (“Subarray Sum Equals K”), but instead of integer sums, we are counting occurrences. We can transform the input array into a binary sequence where odd numbers become 1 and even numbers become 0.
The goal becomes finding subarrays with a sum equal exactly to k. Using a Prefix Count strategy:
- Maintain a running count (
odd_count) of odds encountered so far as we iterate. - For any current index, if the total odd count is , and there exists a previous prefix where the odd count was such that , then every subarray starting after that previous point and ending at the current one contains exactly
kodds. - We store how many times each specific cumulative odd count has occurred in a Hash Map (
count_map). This allows us to instantly query how many valid start points exist for any given end position.
Approach
- Initialize: Create a hash map
count_map. Initialize it with{0: 1}because an implicit prefix sum of 0 exists before processing the first element (handling subarrays starting from index 0). - Iterate: Loop through each number in
numsusing a single pass (). - Update Count: If the current number is odd, increment our running
odd_count. Even numbers do not change this count. - Check Validity: Calculate
target = odd_count - k.- This target represents the prefix sum we need to have seen previously for a valid subarray ending here.
- If
count_map[target]exists and is greater than 0, add that frequency to our totalresult.
- Update Map: Increment the count in
count_mapfor the currentodd_count, recording this state for future iterations. - Return: Return the accumulated
result.
Complexity Analysis
- Time Complexity: where is the length of
nums. We traverse the array exactly once, and hash map operations (insert/lookup) are amortized . - Space Complexity: . In the worst case, we store frequencies for every possible odd count from 0 to . Since there can be at most distinct counts encountered in a single pass, this fits within memory limits.
Solution
from collections import defaultdict
def numberOfSubarrays(nums: list[int], k: int) -> int:
# Map stores frequency of prefix odd-counts.
# Initialize with {0: 1} to handle subarrays starting from index 0 correctly.
count_map = defaultdict(int)
count_map[0] = 1
odd_count = 0
result = 0
for num in nums:
if num % 2 == 1:
odd_count += 1
# We need a previous prefix sum of (odd_count - k).
# If such a state exists, it means the subarray between that point and now has exactly k odds.
target = odd_count - k
if count_map[target] > 0:
result += count_map[target]
# Record current prefix sum frequency for future windows
count_map[odd_count] += 1
return result
# Example usage matching problem description
print(numberOfSubarrays([1,1,2,1,1], 3)) # Output: 2
print(numberOfSubarrays([2,4,6], 1)) # Output: 0