STEP 10 · SLIDING WINDOW · PARITY COLLAPSE + WINDOW · MEDIUM

Count Number of Nice Subarrays

WHAT IT SAYS

Given an array and a number k, count the subarrays containing exactly k odd numbers.

WHAT IT'S REALLY ASKING

"A 7 and a 3 and a 99 are the same thing here, and so are every 2 and every 400 — the array is a string of 1s and 0s wearing a disguise. Strip it, and a subarray is 'nice' when it contains exactly k ones. Now: what freedom do you have on either end of a block of k odds, and can those two freedoms be chosen independently?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Every subarray, count its odds

O(n²) time, O(1) space

Fix a start, extend right, keep a running tally of how many odd numbers you've swallowed, and tick the answer every time the tally equals k. Restart from the next index. Every subarray gets its odd-count computed, so nothing is missed.

WHERE THE WORK IS WASTED — Three separate redundancies. The tally only ever climbs as you extend, so once it passes k the rest of that inner loop is guaranteed to tick nothing — yet you keep walking. Restarting at i + 1 recomputes the odd-count of s[i+1..r], a number the previous pass already had (it's the old tally minus one indicator). And the ticking itself is done one subarray at a time: when the tally sits at k across a run of trailing evens, brute force re-verifies the count for each of those ends separately, when the run of evens is a single fact you could have read off once.

KEY OBSERVATION — THE UNLOCKlink

Nothing about a number survives but its parity.

The condition mentions only how many odd numbers a subarray contains — never which ones, never how big. So replace every element by 1 if it's odd and 0 if it's even. Any two arrays with the same parity pattern have identical answers, which means the magnitudes carry no information about the problem at all: they're noise you've been dragging through every comparison. What's left after you strip them is a binary array, and 'the subarray has exactly k odds' has become 'the subarray sums to exactly k'. That reframing is the whole unlock — it turns a scattered counting question into a question about how far apart the 1s are.

Prefix odd-counts and a tally of what you've passed

O(n) time, O(n) space

Let C[r] be the number of odds up to r. A subarray ending at r is nice exactly when some earlier prefix had C[r] − k odds, so keep a running frequency map of the prefix counts you've already walked past and add its count at each step (seeding count 0 with frequency 1 for the empty prefix). One pass, and it never looks at where the odds actually sit.

KEY OBSERVATION — THE UNLOCKlink

The evens on each end are free, and independent.

Take any block of k consecutive odds. Walk left from the first of them: every even you cross can be swallowed without changing the odd-count, so each is a legal start — and so is the first odd itself. If there are a evens before the block (i.e. before the first odd, back to the previous odd or the array's edge), you have a + 1 choices of start. Walk right from the last odd of the block: the same argument gives b + 1 choices of end, where b is the run of evens after it. The key word is *independent*: choosing a start doesn't constrain the end, because a start choice only touches the evens on the left and an end choice only touches the evens on the right — the k odds in the middle are untouched by both. Independent choices multiply. So this block contributes exactly (a + 1) × (b + 1) nice subarrays, and every nice subarray arises from exactly one block (its own set of k odds), so there's no double counting. Sum over the blocks and you're done.

Walk the odds, measure the gaps

O(n) time, O(1) extra space beyond the odd positions

Record the positions of the odd numbers as you go (or slide a window holding exactly k of them). Each time the window holds k odds, its contribution is the gap to the previous odd on the left times the gap to the next odd on the right — the two runs of evens, each counted with its +1. Add them all up; if you'd rather not think about blocks at all, the same count falls out of atMost(k) − atMost(k − 1) run on the binary array.

WHAT YOU TRADED — The prefix map buys you generality — it never cares where the odds are, so the same code counts subarrays with a given sum over any integers — and pays O(n) memory for the privilege; the gap-multiplication drops to O(1) working memory but only because the indicator values are non-negative, so a window's odd-count is monotone in its width. The transferable lesson is the first move, not the second: before optimising, ask which parts of an element the problem actually reads, and throw the rest away.

WATCH THE IDEA RUN

nice subarrays 0

free starts at this end 0

k = 2. Forget the values — only the parity is readable. Odds are 1s, evens are 0s, and a nice subarray is one holding exactly 2 ones.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Parity Collapse

YOU'LL SEE IT AGAIN WHEN

The condition only reads a yes/no property of each element (odd, vowel, negative, greater than x) and never its value — so the array is secretly binary and you should relabel it before doing anything else.
You're counting subarrays that contain exactly k of some marked element, and the unmarked elements sit between the marks costing nothing.
For a given right end, the valid starts form a contiguous run rather than a single index, because the boundary elements are free.
The quantity being counted only grows as the window widens — so 'at most k' slides even when 'exactly k' doesn't.

SAME BLUEPRINT, DIFFERENT PROBLEM

Binary Subarrays With SumSubarray Sum Equals KSubarrays with K Different IntegersNumber of Substrings Containing All Three Characters

The bar isn't "solved it once." It's "could rebuild it from the observation."