Problem Description

You are given an array of integers nums and an integer k. Your task is to find how many continuous subarrays contain exactly k odd numbers. These subarrays are called "nice" subarrays.

A subarray is a contiguous part of the array, and you need to count all possible subarrays where the total count of odd numbers equals k.

For example, if nums = [1, 1, 2, 1, 1] and k = 3, you would look for all subarrays that have exactly 3 odd numbers. The subarrays [1, 1, 2, 1] and [1, 2, 1, 1] both contain exactly 3 odd numbers (the even number 2 doesn't affect the odd count).

The solution uses a prefix sum technique combined with a hash table. As we traverse the array, we keep track of the cumulative count of odd numbers seen so far (t). The key insight is that if we have seen t odd numbers up to the current position, and we want subarrays with exactly k odd numbers, we need to find how many prefix arrays had t - k odd numbers. The difference between these two positions would give us a subarray with exactly k odd numbers.

The code uses v & 1 to check if a number is odd (this bitwise operation returns 1 for odd numbers and 0 for even numbers). The Counter is initialized with {0: 1} to handle the case where a subarray starts from the beginning of the array. For each element, we update the running count of odd numbers, check how many valid subarrays end at the current position by looking up cnt[t - k], and then update our counter for future positions.

Intuition

The key observation is that we need to count subarrays with exactly k odd numbers. Instead of checking every possible subarray (which would be inefficient), we can transform this into a different problem: tracking the cumulative count of odd numbers as we traverse the array.

Think of it this way: if we know how many odd numbers we've seen up to position i and how many we've seen up to position j (where j < i), then the subarray from j+1 to i contains the difference between these two counts. So if we've seen t odd numbers up to position i, we want to find all positions j where we had seen t - k odd numbers. Each such position gives us a valid subarray.

This transforms our problem from "finding subarrays with exactly k odd numbers" to "finding pairs of positions whose odd-count difference is k". This is a classic pattern where we can use a hash table to store the frequency of each odd-count we've encountered.

Why does this work? Consider walking through the array and maintaining a running count of odd numbers. At each position, if our current count is t, then any previous position with count t - k can be the start of a valid subarray ending at our current position. By storing how many times we've seen each count value, we can instantly know how many valid subarrays end at the current position.

The initialization {0: 1} handles the edge case where a valid subarray starts from the very beginning of the array. Without this, we'd miss counting subarrays that start at index 0 and have exactly k odd numbers.

Learn more about Math, Prefix Sum and Sliding Window patterns.

Solution Approach

The solution implements a prefix sum technique combined with a hash table to efficiently count subarrays with exactly k odd numbers.

Data Structures Used:

• A Counter (hash table) cnt to store the frequency of each prefix sum value
• Variables ans to store the final count and t to track the running count of odd numbers

Algorithm Steps:

1. Initialize the counter: Start with cnt = Counter({0: 1}). The key 0 with value 1 means we've seen zero odd numbers once (before processing any elements). This handles subarrays starting from index 0.

2. Traverse the array: For each number v in nums:

   • Update odd count: Add v & 1 to t. The bitwise AND operation v & 1 returns 1 if v is odd (last bit is 1) and 0 if v is even (last bit is 0).

   • Count valid subarrays: Look up cnt[t - k] and add it to ans. This represents how many times we've previously seen t - k odd numbers. Each such occurrence means there's a subarray ending at the current position with exactly k odd numbers.

   • Update the counter: Increment cnt[t] by 1 to record that we've now seen t odd numbers up to this position.

3. Return the result: After processing all elements, ans contains the total count of nice subarrays.

Why This Works: If we have t odd numbers up to the current position and we previously had t - k odd numbers at some earlier position(s), then the subarray between those positions contains exactly t - (t - k) = k odd numbers. The hash table allows us to look up how many such earlier positions exist in O(1) time, making the overall algorithm O(n) in time complexity with O(n) space complexity for the hash table.

Example Walkthrough

Let's trace through the algorithm with nums = [1, 1, 2, 1, 1] and k = 3.

Initial State:

• cnt = {0: 1} (we've seen 0 odd numbers once, before starting)
• ans = 0 (no subarrays counted yet)
• t = 0 (running count of odd numbers)

Step 1: Process nums[0] = 1

• 1 & 1 = 1 (1 is odd), so t = 0 + 1 = 1
• Check cnt[t - k] = cnt[1 - 3] = cnt[-2] = 0 (no previous position with -2 odd numbers)
• ans = 0 + 0 = 0
• Update cnt[1] = 1
• State: cnt = {0: 1, 1: 1}, ans = 0, t = 1

Step 2: Process nums[1] = 1

• 1 & 1 = 1 (1 is odd), so t = 1 + 1 = 2
• Check cnt[2 - 3] = cnt[-1] = 0
• ans = 0 + 0 = 0
• Update cnt[2] = 1
• State: cnt = {0: 1, 1: 1, 2: 1}, ans = 0, t = 2

Step 3: Process nums[2] = 2

• 2 & 1 = 0 (2 is even), so t = 2 + 0 = 2
• Check cnt[2 - 3] = cnt[-1] = 0
• ans = 0 + 0 = 0
• Update cnt[2] = 2 (we've now seen 2 odd numbers at two positions)
• State: cnt = {0: 1, 1: 1, 2: 2}, ans = 0, t = 2

Step 4: Process nums[3] = 1

• 1 & 1 = 1 (1 is odd), so t = 2 + 1 = 3
• Check cnt[3 - 3] = cnt[0] = 1 ✓ (Found 1 valid subarray!)
  • This means subarray from start to current position [1,1,2,1] has exactly 3 odd numbers
• ans = 0 + 1 = 1
• Update cnt[3] = 1
• State: cnt = {0: 1, 1: 1, 2: 2, 3: 1}, ans = 1, t = 3

Step 5: Process nums[4] = 1

• 1 & 1 = 1 (1 is odd), so t = 3 + 1 = 4
• Check cnt[4 - 3] = cnt[1] = 1 ✓ (Found 1 valid subarray!)
  • This means subarray from after index 0 to current position [1,2,1,1] has exactly 3 odd numbers
• ans = 1 + 1 = 2
• Update cnt[4] = 1
• State: cnt = {0: 1, 1: 1, 2: 2, 3: 1, 4: 1}, ans = 2, t = 4

Final Result: 2

The algorithm correctly identifies two subarrays with exactly 3 odd numbers:

1. [1, 1, 2, 1] - found when processing index 3
2. [1, 2, 1, 1] - found when processing index 4

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array nums exactly once. In each iteration, it performs constant-time operations:

• Checking if a number is odd using v & 1 - O(1)
• Accessing and updating the counter dictionary - O(1) on average
• Arithmetic operations for updating t and ans - O(1)

Since we traverse all n elements once with constant-time operations per element, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the Counter dictionary cnt. In the worst case, when all elements in the array are odd, the variable t (which counts odd numbers) can have n + 1 different values (from 0 to n). This means the counter dictionary could store up to n + 1 key-value pairs. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Initialize the Counter with {0: 1}

The Pitfall: A common mistake is initializing an empty Counter without the base case {0: 1}. This causes the algorithm to miss subarrays that start from the beginning of the array.

Why it happens: When we have exactly k odd numbers from the start of the array, we need to count this as a valid subarray. Without {0: 1}, when odd_count = k, looking up prefix_count[k - k] = prefix_count[0] would return 0 instead of 1.

Example of the bug:

# WRONG - Missing subarrays starting at index 0
prefix_count = Counter()  # Empty counter

Correct approach:

# CORRECT - Handles subarrays from the beginning
prefix_count = Counter({0: 1})

2. Incorrect Order of Operations

The Pitfall: Updating prefix_count[odd_count] before checking prefix_count[odd_count - k] can lead to overcounting when k = 0.

Why it happens: When k = 0, we're looking for subarrays with no odd numbers. If we increment prefix_count[odd_count] first, then check prefix_count[odd_count - 0], we'd be counting the current position itself as a valid subarray endpoint, which is incorrect.

Example of the bug:

# WRONG - Order matters when k = 0
for num in nums:
    odd_count += num & 1
    prefix_count[odd_count] += 1  # Updated first
    result += prefix_count[odd_count - k]  # Then checked - causes overcounting

Correct approach:

# CORRECT - Check first, then update
for num in nums:
    odd_count += num & 1
    result += prefix_count[odd_count - k]  # Check first
    prefix_count[odd_count] += 1  # Then update

3. Using Wrong Method to Check Odd Numbers

The Pitfall: Using modulo operator incorrectly or with wrong precedence can give incorrect results.

Example of the bug:

# WRONG - Operator precedence issue
odd_count += num % 2 == 1  # Returns True/False, not 0/1 consistently

# WRONG - Doesn't handle negative numbers correctly
odd_count += num % 2  # -3 % 2 = -1 in Python, not 1

Correct approaches:

# CORRECT - Bitwise AND always works
odd_count += num & 1

# CORRECT - Explicit conversion if using modulo
odd_count += 1 if num % 2 != 0 else 0

# CORRECT - Taking absolute value for modulo
odd_count += abs(num) % 2