Count the number of subarrays with exactly k odd numbers.

Medium

📘 Problem Statement

Given an array of integers nums and an integer k. Return the number of sub-arrays which has exactly k odd numbers.

🔍 Example

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.

Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2

Output: 16

🛠️ Solution

❌ Brute Force Approach (Inefficient)

  • Try all possible subarrays and count how many odd numbers are in each.
  • If a subarray contains exactly k odd numbers, increment the count.
def numberOfSubarrays(nums, k):
    count = 0
    n = len(nums)

    for i in range(n):
        odd_count = 0
        for j in range(i, n):
            if nums[j] % 2 == 1:
                odd_count += 1
            if odd_count == k:
                count += 1
            elif odd_count > k:
                break  # optimization
    return count

The total complexity of this solution is O(n2)O(n^2). Not efficient for large arrays.

⚡ Optimized Approach: Prefix Sum

This approach is similar to the Subarray Sum equals K, with the change being instead of counting the sum, we will transform the problem to count the number of odd numbers seen so far.

💡 Key Idea:

  1. Transform the problem:

    Count how many odds have been seen up to each index using a prefix sum. Let odd_count_so_far be the number of odd numbers encountered up to current index. We want to find how many subarrays have:

    odd_count_right − odd_count_left = k

  2. Track frequency of odd counts using a hashmap:

  • Let count_map[i] store how many times i odd numbers have been seen.

  • For each position, check if odd_count - k has been seen before — this means there exists a previous subarray whose difference in odd count is exactly k.

📘 Why This Works ?

We track:

  • For each index i, how many subarrays ending at i contain exactly k odd numbers.

  • Whenever prefix_odds - k has occurred before, it means we can form a subarray from that earlier index to current index with exactly k odds.

def numberOfSubarrays(nums, k):
    from collections import defaultdict

    count = 0
    prefix_odds = 0
    freq = defaultdict(int)
    freq[0] = 1  # base case: 0 odd numbers seen at the start

    for num in nums:
        if num % 2 == 1:
            prefix_odds += 1

        count += freq[prefix_odds - k]
        freq[prefix_odds] += 1

    return count

⏱️ Time & Space Complexity

Operation Complexity
Time O(n)O(n)
Space O(n)O(n)