Count Number of Nice Subarrays: Prefix Count Pattern

LeetCode #1248, Count Number of Nice Subarrays, asks you to count contiguous subarrays that contain exactly k odd numbers. A subarray with exactly k odd numbers is called "nice." At first glance this feels like a sliding window problem, but there is an even cleaner approach: reduce it to the classic "subarray sum equals k" problem using a prefix count and a hash map.

Why this problem matters

The prefix count technique is one of the most versatile tools for subarray counting problems. Once you see that "count subarrays with exactly k odd numbers" is the same as "count subarrays with sum exactly k" after a parity transformation, the solution follows directly from the Subarray Sum Equals K pattern. This reduction shows up repeatedly. Binary Subarrays With Sum uses the same idea on arrays of 0s and 1s. Problems involving "exactly k" of some property in a subarray often reduce to prefix sums plus a hash map.

Learning to spot these reductions is more valuable than memorizing individual solutions. The underlying building block, prefix sum + hash map for subarray counting, covers a wide family of problems.

The key insight

Replace each element with 1 if it is odd and 0 if it is even. Now the array is binary, and the sum of any subarray equals the count of odd numbers in that subarray. The problem becomes: count subarrays with sum exactly k.

This is exactly the Subarray Sum Equals K problem (LeetCode #560). You maintain a running count of odd numbers seen so far (which acts as the prefix sum), and you use a hash map to record how many times each prefix odd count has appeared. For each new position, you check how many earlier positions had a prefix odd count of current_count - k. Each such earlier position marks the start of a nice subarray ending at the current position.

The solution

from collections import defaultdict

def numberOfSubarrays(nums, k):
    prefix_count = defaultdict(int)
    prefix_count[0] = 1
    odd_count = 0
    result = 0

    for num in nums:
        odd_count += num % 2
        result += prefix_count[odd_count - k]
        prefix_count[odd_count] += 1

    return result

Here is how the pieces fit together:

1. Seed the map with {0: 1}. Before processing any element, the running odd count is 0. If the odd count ever reaches exactly k, then odd_count - k = 0, and the map needs to report that 0 was seen once. Without this seed, you would miss nice subarrays that start from index 0.

2. Track the running odd count. For each element, add num % 2 to the running total. This adds 1 for odd numbers and 0 for even numbers.

3. Look up odd_count - k in the map. If some earlier position had an odd count equal to odd_count - k, then the subarray from just after that position to the current position contains exactly k odd numbers. The frequency in the map tells you how many such subarrays end here.

4. Record the current odd count. Increment its frequency in the map so future positions can reference it.

The order matters: check the map before updating it. This prevents counting a zero-length "subarray" by comparing a prefix count against itself.

Visual walkthrough

Let's trace through nums = [2, 1, 2, 1, 1] with k = 2. The running odd count grows each time we encounter an odd number, and the hash map tells us how many earlier positions had the right count.

The algorithm finds all four nice subarrays: [2, 1, 2, 1], [1, 2, 1], [1, 2, 1, 1], and [2, 1, 1]. Each one contains exactly 2 odd numbers.

Complexity analysis

Time: O(n). You iterate through the array once. Each hash map lookup and insertion is O(1) on average. The total work is linear in the size of the input.

Space: O(n). The hash map stores prefix odd counts. In the worst case (all odd or all even), the number of distinct prefix counts is n + 1, so the map holds at most n + 1 entries.

The building blocks

1. Prefix odd count as prefix sum

The transformation from "count odd numbers" to "prefix sum" is the core reduction. By treating each element as num % 2, you convert the problem into one where standard prefix sum machinery applies.

odd_count = 0
for num in nums:
    odd_count += num % 2

This is the same as computing a prefix sum over a binary array. The value odd_count at position j equals the number of odd elements in nums[0..j].

2. Hash map for complement lookup

The hash map stores how many times each prefix odd count has been seen. When you want to know how many subarrays ending at the current position have exactly k odd numbers, you look up odd_count - k in the map.

prefix_count = defaultdict(int)
prefix_count[0] = 1
for num in nums:
    odd_count += num % 2
    result += prefix_count[odd_count - k]
    prefix_count[odd_count] += 1

This is the same hash map pattern used in Subarray Sum Equals K, Two Sum, and many other "find a complement" problems. The frequency count handles the case where multiple earlier positions produce the same prefix sum.

Edge cases

• All elements are odd. Every element contributes 1 to the running count. The number of nice subarrays is n - k + 1 when k is at most n, and 0 otherwise.
• All elements are even. The running odd count stays at 0 forever. If k = 0, every subarray is nice (there are n * (n + 1) / 2 of them). If k > 0, the answer is 0.
• k = 0. You are counting subarrays with no odd numbers at all. The algorithm handles this naturally because it looks up odd_count - 0 = odd_count in the map, which counts subarrays between positions with the same prefix odd count (meaning no new odd numbers appeared between them).
• Single element. If the single element is odd and k = 1, the answer is 1. If it is even and k = 0, the answer is 1. Otherwise the answer is 0.
• k exceeds the total number of odd elements. The running odd count never reaches k, so odd_count - k is always negative and never found in the map. The answer is 0.

From understanding to recall

The prefix count + hash map pattern for this problem is compact: four lines inside the loop. But the details matter. You need to seed the map with {0: 1}. You need to check the map before updating it. You need to use num % 2 rather than checking odd/even with a branch.

These details are easy to understand but surprisingly easy to forget under pressure. Spaced repetition locks them into long-term memory. After a few review sessions where you write the solution from scratch, the pattern becomes automatic. You see "count subarrays with exactly k of some property" and the reduction to prefix sum + hash map flows out without hesitation.

The real payoff comes from transfer. Once this pattern is second nature, problems like Binary Subarrays With Sum, Subarray Sums Divisible by K, and Contiguous Array all feel like variations on the same theme. You are not memorizing five separate solutions. You are drilling one building block that unlocks all of them.

Related posts

• Subarray Sum Equals K - The foundational prefix sum + hash map problem that this reduces to
• Binary Subarrays With Sum - Same prefix count technique on binary arrays
• Subarrays with K Different Integers - Another "exactly k" subarray counting problem

CodeBricks breaks Count Number of Nice Subarrays into its prefix odd count and hash map complement lookup building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the reduction is automatic. When a subarray counting problem shows up in your interview, you spot the pattern and write the solution without second-guessing the details.