At most k, and exactly k

"How many subarrays contain exactly k distinct values" has no sliding window, and "how many contain at most k" has an obvious one. The counting trick converts the first question into two copies of the second:

exactly(k) = atMost(k) - atMost(k - 1)

Every subarray with at most k distinct values either has at most k − 1, or has exactly k. Subtract the first group from the whole and what remains is the second. The arithmetic is trivial; the reason the window works on one form and not the other is the part to understand.

Why "exactly k" has no window

Fix the right end at r and ask which left ends give a valid subarray.

For at most k distinct, the answer is a suffix. If [l, r] has at most k distinct values then [l + 1, r] does too — dropping an element can never add a distinct value. So there is a smallest valid l, every position from there to r is valid, and everything to its left is not. The predicate flips once as l moves right and stays flipped, which is the monotonicity a shrink loop needs: when the window is invalid, shrinking is the only move, and it always helps.

For exactly k distinct, the valid left ends form a band in the middle. Too far left and the window holds more than k; too far right and it holds fewer. Both ends are invalid, and shrinking fixes one violation while causing the other. There is nothing for while violated: shrink to converge on — the same failure mode as the sliding window over possibly-negative sums, and the same tell: the property is not monotone in the direction the pointer moves.

The band, though, is the difference between two suffixes. That is what the subtraction is doing geometrically.

Subarrays ending at a fixed right end: the at-most-k starts minus the at-most-k-minus-1 starts leave the band that holds exactly k100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Counting the subarrays that end at r

Inside an atMost scan, after the shrink loop the window [l, r] is the largest valid window ending at r. Every valid subarray ending at r starts at one of l, l+1, …, r, and that is

r - l + 1

of them. Add that at every step and the total is exact, because every subarray has exactly one right endpoint, so grouping by right endpoint partitions the whole set — no subarray is counted twice and none is missed.

from collections import defaultdict

def at_most(a: list[int], k: int) -> int:
    """Number of subarrays of a with at most k distinct values."""
    if k < 0:
        return 0                       # nothing has a negative distinct count
    count = defaultdict(int)
    l = total = distinct = 0
    for r, x in enumerate(a):
        count[x] += 1
        if count[x] == 1:
            distinct += 1
        while distinct > k:
            count[a[l]] -= 1
            if count[a[l]] == 0:
                distinct -= 1
            l += 1
        total += r - l + 1
    return total


def exactly(a: list[int], k: int) -> int:
    return at_most(a, k) - at_most(a, k - 1)

The k < 0 guard is not decoration. exactly(a, 0) calls at_most(a, -1), and without the guard the while distinct > -1 loop is true even on an empty window and walks l off the end of the array.

A worked example

Take a = [1, 2, 1, 2, 3] and k = 2.

atMost(2), tracing l and the running total:

r	value	window after shrinking	r − l + 1	total
0	1	[1]	1	1
1	2	[1, 2]	2	3
2	1	[1, 2, 1]	3	6
3	2	[1, 2, 1, 2]	4	10
4	3	[2, 3]	2	12

At r = 4 the incoming 3 makes the window hold three distinct values, so the shrink loop drops indices 0, 1 and 2 — the count of value 1 only reaches zero when the second copy leaves, which is why l ends at 3 and not at 1.

atMost(1) on the same array. No two neighbours are equal, so every window collapses to a single element and each step contributes 1: the total is 5.

exactly(2) = 12 - 5 = 7

Check it by hand, naming subarrays by their index range: 0–1, 0–2, 0–3, 1–2, 1–3, 2–3 and 3–4 all hold exactly two distinct values, and nothing else does — seven. The array has 5 × 6 ÷ 2 = 15 subarrays in total; 12 have at most two distinct values, so 3 have three, and those are the three ranges ending at index 4 that start at 0, 1 or 2. Every number agrees.

Cost: two linear passes, so about 2n steps. At n = 10⁵ that is 200,000 operations against the 5 × 10⁹ of enumerating every subarray and counting its distinct values — which would be worse still, since counting is itself O(n).

When the subtraction is not allowed

The identity needs the two families to be nested and integer-stepped: everything atMost(k - 1) counts, atMost(k) counts too, and the bounded quantity moves in whole steps, so "at most k but not at most k − 1" is "equal to k". The difference of the counts is then the count of the difference. Any integer quantity qualifies — distinct values, odds, zeros, character occurrences:

• exactly k odd numbers = at most k odds − at most k − 1 odds.
• exactly k zeros = at most k zeros − at most k − 1 zeros.

A second, independent condition decides whether either side is computable: a shrink loop needs the bounded quantity non-decreasing as the window grows. Nesting makes the subtraction legal; window growth makes it runnable.

Sums with negatives fail only the second. The families stay nested, {sum ≤ S − 1} inside {sum ≤ S} whatever the signs, and on a = [3, -1, 2, -2, 4] 11 of the 15 subarrays have sum ≤ 3 and 9 have sum ≤ 2, a difference of 2, exactly how many sum to 3. The identity holds; what fails is evaluating it in linear time, because no shrinking window computes atMost(S) when the sum can drop as the window grows.

A real-valued quantity breaks the first condition: "the window average is exactly k" is not atMost(k) − atMost(k − 1), since that difference counts every window whose average lands anywhere in (k − 1, k], not just those at k.

The other misuse is reaching for it when you do not need it. atMost alone answers longest window with at most k distinct: it is max(r - l + 1) inside the same loop. The subtraction is only for counting questions, and the give-away word is "how many". The window itself is the two-pointer same-direction shape with a counts map bolted on.

In an interview

Say why the direct window fails before you write the subtraction, or the trick reads as memorised: "exactly k is not monotone in the left pointer — moving left in gives too few distinct values and moving it out gives too many — so I count at most k and at most k − 1 and subtract."

Then justify r - l + 1 explicitly. "After shrinking, [l, r] is the longest valid window ending at r, so the valid subarrays ending at r are exactly the r − l + 1 suffixes of it, and summing over r counts each subarray once because each has one right end."

The mistake that loses points: adding r - l + 1 before the shrink loop rather than after, which counts windows that break the invariant. On the trace above it adds 5 at r = 4 instead of 2, crediting three ranges that hold three distinct values, and atMost(2) comes out as 15 — every subarray in the array — instead of 12.

Check yourself

Why can a shrink loop maintain "at most k distinct" but not "exactly k distinct"?

Dropping an element can only reduce the distinct count, so "at most k" flips from false to true once as the left pointer advances and stays true — a monotone predicate. "Exactly k" is violated on both sides: shrinking fixes a window with too many distinct values and breaks one with too few, so the loop has no direction to converge in.

In an atMost scan the window after shrinking is [3, 9]. How many valid subarrays end at index 9, and why is summing that over every r not double-counting?

9 − 3 + 1 = 7, one per start position from 3 to 9. Each subarray has exactly one right endpoint, so grouping by r partitions the set of subarrays; nothing is counted twice.

You are asked for the number of subarrays whose sum is exactly S, and the values may be negative. Does atMost(S) - atMost(S - 1) work?

Not as a computation. With negatives the window sum is not monotone as the window grows, so there is no atMost window to run in the first place. Use prefix sums with a hash map of counts instead.