Subarrays with K Different Integers
hardTime: O(n)Space: O(n)
Recognize the pattern
count subarrays with exactly k distinct integersexact = atMost(k) - atMost(k-1)sliding window trick
Brute force idea
Check every subarray — O(n²).
Better approach
exactly(k) = atMost(k) - atMost(k-1). atMost(k) uses a sliding window counting subarrays with ≤ k distinct values. O(n) per atMost call, O(n) total.
Key invariant
Counting 'exactly k' directly is hard with a sliding window. But 'at most k' minus 'at most k-1' gives 'exactly k' — and 'at most k' is a standard sliding window problem.
Watch out for
Trying to directly count 'exactly k' with a single window — the window can grow and shrink unpredictably. The subtraction trick avoids this.