LeetCode 1248 - Count Number of Nice Subarrays

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many contiguous subarrays contain exactly k odd numbers.

We are given an integer array nums and an integer k. A subarray is any continuous segment of the array, meaning the elements must appear next to each other in the original order. A subarray is considered "nice" if it contains exactly k odd integers.

The task is not to find the subarrays themselves, but to return the total number of valid subarrays.

For example, in the array [1,1,2,1,1] with k = 3, the valid subarrays are:

[1,1,2,1]
[1,2,1,1]

So the answer is 2.

The constraints are important:

The array can contain up to 50,000 elements.
Each value can be as large as 10^5.

Because the input size is large, an algorithm with quadratic complexity, O(n^2), will be too slow in the worst case. We need a solution closer to linear time.

An important observation is that the actual values of the even numbers do not matter. The only thing that matters is whether each number is odd or even. This allows us to transform the problem into counting subarrays whose cumulative odd count equals k.

Several edge cases are worth considering:

Arrays with no odd numbers at all.
Arrays where every number is odd.
Cases where k equals 1.
Cases where the entire array contains exactly k odd numbers.
Long stretches of even numbers before, after, or between odd numbers.

These situations can easily expose off by one errors in sliding window or prefix sum implementations.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

For each starting index, we expand the ending index one step at a time and count how many odd numbers appear in that subarray. Whenever the odd count becomes exactly k, we increment the answer.

This approach is correct because it explicitly checks every contiguous subarray and counts all valid ones.

However, there are O(n^2) possible subarrays. With n = 50,000, this becomes far too slow. Even with some small optimizations, the worst case remains quadratic.

Optimal Approach, Prefix Sum with Hash Map

The key insight is that we do not care about the exact numbers, only about how many odd numbers have appeared so far.

We define:

prefixOddCount = number of odd elements seen from the start up to the current index.

If at some index the current prefix contains x odd numbers, then any earlier prefix with x - k odd numbers forms a subarray containing exactly k odd numbers.

This transforms the problem into a prefix sum counting problem.

We use a hash map to store how many times each prefix odd count has appeared. As we iterate through the array:

Update the current odd count.
Check how many previous prefixes had count currentOddCount - k.
Add that frequency to the answer.
Store the current prefix count in the hash map.

This gives a linear time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal	O(n)	O(n)	Uses prefix sums and a hash map

Algorithm Walkthrough

Initialize a hash map called prefix_counts.

This map stores how many times each prefix odd count has occurred. We begin with:

prefix_counts[0] = 1

This represents the empty prefix before processing any elements. 2. Initialize three variables:

current_odd_count = 0
nice_subarrays = 0
prefix_counts = {0: 1}

Iterate through the array one number at a time.
For each number, determine whether it is odd.

If num % 2 == 1, increment current_odd_count. 5. Compute:

needed = current_odd_count - k

If we have previously seen a prefix with exactly needed odd numbers, then the subarray between that prefix and the current index contains exactly k odd numbers. 6. Add the frequency of needed from the hash map to the answer.

nice_subarrays += prefix_counts.get(needed, 0)

Record the current prefix odd count in the hash map.

prefix_counts[current_odd_count] += 1

Continue until the entire array has been processed.
Return the final count.

Why it works

The algorithm works because the difference between two prefix odd counts equals the number of odd elements inside the subarray between them.

If:

current_odd_count - previous_odd_count = k

then the subarray between those two positions contains exactly k odd numbers.

By storing how many times each prefix count has occurred, we can efficiently count all valid subarrays ending at every index.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1
        
        current_odd_count = 0
        nice_subarrays = 0
        
        for num in nums:
            if num % 2 == 1:
                current_odd_count += 1
            
            needed = current_odd_count - k
            
            nice_subarrays += prefix_counts[needed]
            
            prefix_counts[current_odd_count] += 1
        
        return nice_subarrays

The implementation closely follows the algorithm described above.

We use defaultdict(int) so missing keys automatically return 0. This avoids repeated existence checks.

The variable current_odd_count tracks how many odd numbers have appeared so far while traversing the array.

For every element:

If the number is odd, increment the prefix odd count.
Compute how many earlier prefixes would create a subarray containing exactly k odd numbers.
Add the number of matching prefixes to the answer.
Store the current prefix count for future subarrays.

The initialization:

prefix_counts[0] = 1

is extremely important. It allows subarrays starting at index 0 to be counted correctly.

Go Solution

func numberOfSubarrays(nums []int, k int) int {
    prefixCounts := make(map[int]int)
    prefixCounts[0] = 1

    currentOddCount := 0
    niceSubarrays := 0

    for _, num := range nums {
        if num%2 == 1 {
            currentOddCount++
        }

        needed := currentOddCount - k

        if count, exists := prefixCounts[needed]; exists {
            niceSubarrays += count
        }

        prefixCounts[currentOddCount]++
    }

    return niceSubarrays
}

The Go implementation is nearly identical to the Python version conceptually.

The main difference is that Go maps return two values during lookup:

value, exists := map[key]

This is used to safely check whether the required prefix count exists.

Go integers are sufficient for this problem because the maximum number of subarrays is well within 32 bit signed integer range, although Go's int type already handles this comfortably on modern systems.

Worked Examples

Example 1

Input:

nums = [1,1,2,1,1]
k = 3

Index	Num	Odd?	Current Odd Count	Needed	Matching Prefixes	Answer
Start	-	-	0	-	prefix_counts[0] = 1	0
0	1	Yes	1	-2	0	0
1	1	Yes	2	-1	0	0
2	2	No	2	-1	0	0
3	1	Yes	3	0	1	1
4	1	Yes	4	1	1	2

Final answer:

The two valid subarrays are:

[1,1,2,1]
[1,2,1,1]

Example 2

Input:

nums = [2,4,6]
k = 1

Index	Num	Odd?	Needed
0	2	No	-1
1	4	No	-1
2	6	No	-1

Final answer:

There are no odd numbers, so no valid subarrays exist.

Example 3

Input:

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

The odd numbers occur at indices:

3 and 6

Any subarray containing exactly those two odd numbers is valid.

There are:

4 choices for the left boundary
4 choices for the right boundary

So the total is:

4 × 4 = 16

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once
Space	O(n)	Hash map may store up to n distinct prefix counts

The algorithm performs a single pass through the array, making it linear in time complexity.

The hash map stores frequencies of prefix odd counts. In the worst case, every element is odd, so the prefix counts range from 0 to n, requiring linear additional space.

Test Cases

from typing import List

def test_solution():
    sol = Solution()

    assert sol.numberOfSubarrays([1,1,2,1,1], 3) == 2
    # Standard example with multiple valid subarrays

    assert sol.numberOfSubarrays([2,4,6], 1) == 0
    # No odd numbers exist

    assert sol.numberOfSubarrays([2,2,2,1,2,2,1,2,2,2], 2) == 16
    # Large even stretches around odd numbers

    assert sol.numberOfSubarrays([1], 1) == 1
    # Single odd element

    assert sol.numberOfSubarrays([2], 1) == 0
    # Single even element

    assert sol.numberOfSubarrays([1,1,1,1], 2) == 3
    # All numbers odd

    assert sol.numberOfSubarrays([1,2,1,2,1], 2) == 4
    # Alternating odd and even numbers

    assert sol.numberOfSubarrays([2,2,1,2,2], 1) == 9
    # One odd number with many surrounding evens

    assert sol.numberOfSubarrays([1,2,3,4,5], 3) == 1
    # Entire array contains exactly k odds

    assert sol.numberOfSubarrays([1,2,1,2,1,2,1], 3) == 6
    # Multiple overlapping valid subarrays

test_solution()

Test	Why
`[1,1,2,1,1], k=3`	Basic example with overlapping answers
`[2,4,6], k=1`	No valid subarrays
`[2,2,2,1,2,2,1,2,2,2], k=2`	Long even stretches
`[1], k=1`	Smallest valid input
`[2], k=1`	Smallest invalid input
`[1,1,1,1], k=2`	Every number is odd
`[1,2,1,2,1], k=2`	Alternating parity
`[2,2,1,2,2], k=1`	Many combinations around one odd
`[1,2,3,4,5], k=3`	Entire array valid
`[1,2,1,2,1,2,1], k=3`	Multiple overlapping windows

Edge Cases

One important edge case occurs when the array contains no odd numbers at all. In this situation, the prefix odd count never increases. A buggy implementation might incorrectly count subarrays even though none satisfy the requirement. The current solution handles this correctly because current_odd_count - k never matches any valid prefix count when k > 0.

Another tricky case happens when every number is odd. In this scenario, the prefix odd count increases at every step. This tests whether the implementation correctly counts overlapping subarrays. Since the algorithm relies purely on prefix differences, it naturally handles overlapping ranges without double counting.

A third important edge case involves large stretches of even numbers surrounding the odd numbers. For example:

[2,2,2,1,2,2,1,2,2]

The valid subarrays come from many combinations of left and right boundaries. Naive implementations often miss these combinations. The prefix sum approach counts all of them automatically because every matching earlier prefix contributes another valid starting position.

A final subtle edge case occurs when a valid subarray starts at index 0. Without initializing:

prefix_counts[0] = 1

those subarrays would never be counted. The initialization represents the empty prefix before the array begins and ensures correctness for prefixes that themselves contain exactly k odd numbers.