Count windows via at-most(k) trick

48 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Count the stretches of 1, 2, 1, 2, 3 that contain exactly two different values. By hand you list every stretch and check: (1,2), (2,1), (1,2), (2,3), (1,2,1), (2,1,2), (1,2,1,2) qualify, so the answer is 7. That is O(n²) stretches each checked in O(n).

A sliding window seems natural, but "exactly two" is awkward: it does not survive growing (a third value may appear) or shrinking (a value may disappear). The windows that are easy to count are the ones whose condition is "at most".

Build the structure, one piece at a time

Piece one: learn to count windows with at most k distinct values. Keep a window [l, r] with a count table. Grow r; while the window has more than k distinct values, shrink l. Now every start between l and r gives a valid window ending at r, so add r − l + 1 to the count.

Piece two: the subtraction. A window with exactly k distinct values is one that has at most k but not at most k − 1:

exactly(k) = atMost(k) − atMost(k − 1)

Run the same routine with k = 1: windows with a single value are the five singletons, so atMost(1) = 5. Then exactly(2) = 12 − 5 = 7, matching the by-hand count.

The same two pieces count "subarrays with exactly k odd numbers" (atMost counts windows with at most k odds), "binary subarrays with sum s" (atMost(s) − atMost(s − 1)), and "substrings containing all three letters" (total substrings minus those containing at most two).

Why it is correct

For atMost: after the shrink loop, [l, r] has at most k distinct values and [l − 1, r] has more than k (that is why l stopped there, or l = 0). Any start s ≥ l gives a sub-window of a valid window, which has at most as many distinct values, so it is valid; any start s < l gives a super-window of an invalid one, so it is invalid. Hence exactly r − l + 1 valid windows end at r, and summing over r counts each valid window once, by its right end.

For the subtraction: every window with at most k values has either exactly k or at most k − 1, never both. So the set counted by atMost(k) splits cleanly into the two, and subtracting the second leaves the first.

Why it is fast

One atMost pass is a standard window: r moves n times, l moves at most n times, O(n). Two passes are still O(n), with O(k) memory for the count table. Checking every stretch was O(n²) or worse. The cost of "exactly" is one extra pass, which is why the trick is worth memorising: it converts a non-monotone condition into two monotone ones.

How to recognise it in an interview

Cues: "count the subarrays with exactly …", "number of substrings that contain …", where the natural window condition is "at most". If the asked condition is itself "at most" or "at least", one pass is enough; "exactly" needs the subtraction. The first thing to say: "Exactly k equals at most k minus at most k − 1, and at-most windows I can count by adding r − l + 1 at each right end."

Subarrays with K Different Integers is the example. Count Number of Nice Subarrays counts odd numbers instead of distinct values. Binary Subarrays With Sum uses a running sum as the window measure, with the same subtraction.

02The idea in one line

exactly(k) = atMost(k) − atMost(k−1); each window end adds r−l+1 subarrays.

Reach for it when: Count subarrays with exactly k distinct / k odd numbers / sum constraints.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Subarrays with K=2 distinct on [1,2,1,2,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. exactly(k) = atMost(k) − atMost(k−1); each r adds r−l+1 windows
2. atMost(2): r=0, l=0 → +1 windows, total 1
3. atMost(2): r=1, l=0 → +2 windows, total 3
4. atMost(2): r=2, l=0 → +3 windows, total 6
5. atMost(2): r=3, l=0 → +4 windows, total 10
6. atMost(2): r=4, shrink to l=3 → +2 windows, total 12
7. atMost(2) = 12: every window with at most two distinct values
8. atMost(1): r=0, l=0 → +1 windows, total 1
9. atMost(1): r=1, shrink to l=1 → +1 windows, total 2
10. atMost(1): r=2, shrink to l=2 → +1 windows, total 3
11. atMost(1): r=3, shrink to l=3 → +1 windows, total 4
12. atMost(1): r=4, shrink to l=4 → +1 windows, total 5
13. exactly(2) = 12 − 5 = 7
14. Two linear sweeps: O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sliding Window: Fixed-size window, Longest valid window, Shortest satisfying window, Window with a need-counter.