Count Number of Nice Subarrays

An array is nice if it contains exactly k odd numbers. Given an integer array nums and an integer k, return the number of nice contiguous subarrays.

Hints

· Stuck? Reveal one nudge at a time.

Only the parity of each number matters — map odd to 1 and even to 0.

Then 'exactly k odd numbers' is 'sum exactly k' — the same as Binary Subarrays With Sum.

Count it as atMost(k) - atMost(k-1), where atMost(m) windows on the odd count.

Common doubts

Replace odd numbers with 1 and even with 0; a nice subarray is exactly one whose transformed sum is k. The identical atMost identity applies.

Once the window [left, right] has at most m odds, every subarray ending at right and starting in [left, right] also does — that's right - left + 1 of them.

No — they leave the odd count unchanged but still extend valid subarrays, which the right - left + 1 term accounts for.

Interview follow-ups

· What an interviewer asks next.

Track how many prefixes have each odd-count; for the current prefix odd-count c, add the number of earlier prefixes with count c - k. That's an alternate O(n) method.

Then you count subarrays with no odd numbers; the same identity holds with atMost(0) - atMost(-1) = atMost(0).

Fun facts

Nice Subarrays is Binary Subarrays With Sum wearing a parity costume — spotting the disguise is the whole trick.
The odd-as-1 mapping is a special case of 'indicator transform', turning many 'count items with property P' problems into subarray-sum problems.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,1,2,1,1], k = 3
Output: 2
The subarrays with exactly 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
There are 16 subarrays containing exactly 2 odd numbers.

Constraints

- 1 <= nums.length <= 5 * 10^4 - 1 <= nums[i] <= 10^5 - 1 <= k <= nums.length

Replace every odd number with a 1 and every even with a 0, and "exactly k odd numbers" becomes "sum exactly k" — the very same counting problem as Binary Subarrays With Sum. So use the same identity: exactly k = atMost(k) − atMost(k − 1), where atMost(m) counts subarrays with at most m odd numbers via a sliding window.

Prerequisites

Before you start

· Concepts used directly in the solution.

Odd as 1. Treating each odd number as a 1 and each even as a 0 turns the count into a sum.

atMost trick. count(exactly k) = count(at most k) − count(at most k − 1).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The count

“Exactly k odds, or at least k?”

Exactly k — no more, no fewer.

“Do even numbers matter?”

Only as filler — they never change the odd count, but they do extend valid subarrays.

The ideal opening — say it like this

If I map odd to 1 and even to 0, a nice subarray is one whose sum is exactly k.

That's exactly Binary Subarrays With Sum, so I count atMost(k) minus atMost(k-1).

atMost(m) is a window counting subarrays with at most m odd numbers, adding right-left+1 per step.

Understand the problem

Worked example — nums = [1,1,2,1,1], k = 3

odd/even -> [1,1,0,1,1], want sum exactly 3
atMost(3) - atMost(2) = 2
the two nice subarrays are [1,1,2,1] and [1,2,1,1]

Key observations

1Aha

Parity turns this into a sum problem

Map odd -> 1, even -> 0. "Exactly k odd numbers" is "sum exactly k", identical to Binary Subarrays With Sum.

2Aha

atMost(k) − atMost(k − 1)

Counting exactly k directly is hard; two at-most counts subtract to leave precisely the subarrays with k odds.

3Aha

atMost is a clean window on the odd count

Track odds in the window; shrink from the left whenever it exceeds m; add right - left + 1 per step. Even numbers just widen the window for free.

Brute force vs optimal

	Count odds in every subarray	atMost(k) − atMost(k−1)
Idea	Accumulate the odd count per subarray, count == k	Two sliding-window at-most-odds counts, subtracted
Time	O(n^2)	O(n)
Space	O(1)	O(1)

The brute counts odds in every subarray; the identity replaces it with two linear passes. Full code is in the Approaches selector below.

Summary

Key takeaway

Odd = 1, even = 0, and "exactly k odd numbers" is "sum exactly k". Count it as atMost(k) - atMost(k - 1), where atMost(m) slides a window over the odd count, adding right - left + 1 and shrinking when the odd count exceeds m. Two O(n) passes.

def atMost(m):
    if m < 0: return 0
    left = 0; total = 0; odds = 0
    for right in 0 .. n-1:
        if nums[right] is odd: odds += 1
        while odds > m: if nums[left] is odd: odds -= 1; left += 1
        total += right - left + 1
    return total
return atMost(k) - atMost(k - 1)