Subarrays with K Different Integers

Subarrays with k different integers counts subarrays containing exactly k distinct values. A sliding window tracks distinct counts easily, but counting windows with exactly k distinct values directly does not work. The reason is worth understanding. For a given right endpoint, the valid left endpoints form a contiguous range, and finding both of its boundaries requires two separate window positions — the window cannot report both at once. The standard resolution converts the exact count into a difference: - exactly(k) = atMost(k) − atMost(k − 1), because subarrays with at most k distinct values that are not counted by at most k − 1 are precisely those with exactly k. Counting at most k distinct values slides cleanly. Extend the right edge, and while the distinct count exceeds k, shrink from the left. At each position, the number of valid subarrays ending there is right − left + 1 — every left endpoint in the current window produces a valid subarray. That counting step is the part most often written wrong. Adding 1 per position instead of the window width undercounts massively. Within atMost, a value is removed from the frequency map only when its count reaches zero, not on the first decrement. Deleting early miscounts the distinct total. The same identity solves Binary Subarrays with Sum and Count Number of Nice Subarrays — recognising it turns three problems into one technique. Two passes of a linear window give O(n) time and O(k) space.

The same at-most subtraction, now with distinct-count as the window condition. atMost(k) - atMost(k-1) isolates subarrays with exactly k distinct values, and each at-most call is the standard k-distinct window that deletes zero-count keys.