Subarrays with K Different Integers
Return the number of subarrays containing exactly k distinct integers.
Open on LeetCode ↗Intuition
Marked Hard, but the trap is identical to Count Nice Subarrays: trying to slide one window on "exactly k distinct" directly. Exactly-k is not monotone, so there is no shrink rule that keeps the window valid — sometimes adding an element should grow it, sometimes it should have shrunk first, and no single pointer rule covers both. At-most-k is monotone, so compute atMost(k) - atMost(k-1) again, this time over a frequency map instead of a parity count, and don't forget to delete zeroed keys or the map lies about the distinct count.
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.
Approach
See why a single window fails
A window enforcing exactly k distinct has no valid shrink rule: removing an element might drop the distinct count below k, and adding one might push it above. There is no direction that reliably restores legality, which is exactly the property a sliding window requires.
Write atMost(k) over a frequency map
Grow right and increment freq[nums[right]]. While len(freq) > k, decrement the left element's count, delete the key when it reaches zero, and advance left. Add right - left + 1 after each step — that is how many subarrays ending here have at most k distinct values.
Subtract
atMost(k) - atMost(k-1) gives exactly k. Each pass is O(n) with O(k) space for the map, so the total is O(n) — comfortably better than the O(n^2) brute force, and the code is barely longer than the at-most version alone.
Solution & live demo
Common pitfalls
Keeping zero-count keys in the frequency map
freq[out] -= 1 left += 1
if freq[out] == 0:
del freq[out]len(freq) is the validity test, so a key at zero still counts toward distinctness. The window then over-shrinks and both at-most calls return values that are too small.
Trying to count exactly-k with one window
while len(freq) > k: shrink if len(freq) == k: total += 1
return atMost(k) - atMost(k - 1)
For a given right endpoint the valid left endpoints form a contiguous range, not a single position, and finding both its ends needs two pointers. The subtraction gets the same count with one simple window run twice.
Counting one subarray per window position
total += 1
total += right - left + 1
Every subarray ending at right and starting anywhere in [left, right] satisfies at-most-m. That's right - left + 1 subarrays, and the identity depends on counting them all.
Edge cases
atMost(0) is 0, so the answer is simply the count of constant runs.
Both terms coincide and the difference is 0.
len(freq) overstates the distinct count and the window over-shrinks — the same trap as the k-distinct substring problem.
Only k = 1 gives a non-zero answer, namely n(n+1)/2.