< Back 1248. Count Number of Nice Subarrays 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.