This problem is very similar to 560. Instead of finding the number of subarrays that sum to k, we’re finding the number of subarrays that have at most k odd numbers. We simply change the increment of the curr variable to the isOdd constraint, num % 2.
The logic is still the same. The count dictionary maintains the last seen prefix sum that defines the beginning of a subarray that satisfies our constraint. We add the value of count[curr - k] to the result, and mark the current prefix sum as seen.
The solution is as follows:
from collections import defaultdict
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
count = defaultdict(int)
ans = curr = 0
count[0] = 1
for num in nums:
curr += num % 2
ans += count[curr - k]
count[curr] += 1
return ans_ Time Complexity:
O(n) - We iterate through the interger list once.
_ Space Complexity:
O(n) - We store at most n values in the dictionary.