Domain 1548EasyMEDIUM

Count Number of Nice Subarrays

Counts subarrays with exactly k odd numbers by treating odds as 1s and using a hash map to track prefix sum frequencies, achieving linear time complexity.

Domain: medium•Updated: 2026-09-11
#prefix-sum#hash-map#O(N) time complexity

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 N≤50,000N \le 50,000, an O(N2)O(N^2) solution iterating through all subarrays will exceed time limits. We must achieve O(N)O(N) efficiency.

Key Constraints & Edge Cases:

  • Exact Match: The requirement is exactly k odds, 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 k odd 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 CC, and there exists a previous prefix where the odd count was PP such that C−P=kC - P = k, then every subarray starting after that previous point and ending at the current one contains exactly k odds.
  • 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

  1. 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).
  2. Iterate: Loop through each number in nums using a single pass (O(N)O(N)).
  3. Update Count: If the current number is odd, increment our running odd_count. Even numbers do not change this count.
  4. 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 total result.
  5. Update Map: Increment the count in count_map for the current odd_count, recording this state for future iterations.
  6. Return: Return the accumulated result.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the length of nums. We traverse the array exactly once, and hash map operations (insert/lookup) are amortized O(1)O(1).
  • Space Complexity: O(N)O(N). In the worst case, we store frequencies for every possible odd count from 0 to NN. Since there can be at most NN 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