STEP 10 · SLIDING WINDOW · TWO LEFT EDGES · HARD

Subarrays with K Different Integers

WHAT IT SAYS

Given an array and a number k, count the subarrays containing exactly k distinct integers.

WHAT IT'S REALLY ASKING

"Freeze the right end and walk the start rightwards: the number of distinct values you see can only fall, never rise. So the starts sort themselves into three consecutive zones — too many distinct, exactly k, too few — in that order, always. Find the two boundaries between those zones and the middle zone is your answer for this right end, no counting required."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Every subarray, count its distinct values

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

Fix a start, extend right with a frequency map, and tick the answer every time the map holds exactly k keys. Restart from the next index with a fresh map. Every subarray gets measured, so it's correct.

WHERE THE WORK IS WASTED — The distinct-count only climbs as you extend, so once the map has more than k keys every remaining step of that inner loop is guaranteed to tick nothing — yet you keep walking to the end. And the restart at i + 1 rebuilds a map that differed from the finished one by a single decrement. Worst of all, when several consecutive starts all land on exactly k distinct — which happens constantly, whenever the leading element repeats later in the window — brute force re-verifies each of them with its own full scan, when they are one fact with a width.

KEY OBSERVATION — THE UNLOCKlink

Down the starts, distinct-count is a staircase that only descends.

Hold the right end r fixed and think of the start as a dial. Move the dial one step right and you delete one element from the front of the subarray: either it had a duplicate still inside (distinct unchanged) or it didn't (distinct drops by one). It can never rise. So as the start sweeps from 0 to r, the distinct-count is a non-increasing staircase. A non-increasing sequence crosses any threshold exactly once. Which means there is a single cut point `lo` — the first start where the count finally drops to k or below — and a single cut point `hi` — the first start where it drops to k − 1 or below. Every start before `lo` sees too many distinct values; every start at `hi` or beyond sees too few; and everything between them sees *exactly* k. Not approximately: the starts hitting exactly k are precisely `lo` through `hi − 1`, so their number is simply hi − lo. And both cut points behave. Pushing the right end out can only raise the distinct-count of any fixed start, so a start that was already over budget stays over budget forever — neither cut point ever slides backwards. Two left edges, each crossing the array once. (This is where `atMost(k) − atMost(k−1)` comes from, by the way: `lo` is the boundary of the ≤ k window and `hi` is the boundary of the ≤ k−1 window. The subtraction isn't a trick, it's the staircase.)

Run the at-most window twice

O(n) time, O(k) space

Write one routine that counts subarrays with at most k distinct: advance the right edge, crawl the left edge forward while the map holds more than k keys, and add (r − left + 1) at each step, since every start inside the window qualifies. Call it with k and with k − 1 and return the difference.

Fuse it: two left edges, one pass

O(n) time, O(k) space

Carry both windows simultaneously — one shrinking to keep at most k distinct, the other shrinking to keep at most k − 1 — and at every right end add hi − lo to the answer. They need two separate frequency maps, since each edge is at a different position and the counts genuinely differ; sharing one map is the classic bug here. Each pointer still moves forward at most n times, so the whole thing is one linear sweep.

WHAT YOU TRADED — You pay two maps and two left pointers instead of one, and you inherit the usual sliding-window precondition: this only works because distinct-count is monotone in the window's boundaries. The lesson worth carrying: an exact-equality constraint won't drive a single pointer, because its valid starts form a *band* rather than a one-sided region — so express the band as the difference of two one-sided regions, each of which a pointer can chase.

WATCH THE IDEA RUN

0lo hi

subarrays so far 0

exact starts here (hi − lo) 0

k = 2. Two left edges. `lo` is the first start whose window is down to 2 distinct or fewer; `hi` is the first start that has fallen below 2. Everything between them lands exactly.

step 1 / 25

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Staircase Band

YOU'LL SEE IT AGAIN WHEN

You're counting subarrays that hit some quantity exactly, where the quantity is monotone in the window's boundaries — it only rises as the window grows and falls as it shrinks.
For a fixed right end, the qualifying starts form a contiguous band with candidates on both sides of it — too much on one side, too little on the other — so no single pointer can chase the boundary.
The 'at most k' version of the same question is obviously slideable, even though the exact version isn't.
The quantity is integer-valued, so 'at most k' minus 'at most k − 1' isolates 'exactly k' with nothing left over.

SAME BLUEPRINT, DIFFERENT PROBLEM

Binary Subarrays With SumCount Number of Nice SubarraysLongest Substring with At Most K Distinct CharactersCount Complete Subarrays in an Array

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