We need to count all contiguous subarrays that contain exactly k distinct integers. Not "at most k," not "at least k," but precisely k.

The "exactly k" constraint is the source of the difficulty. A sliding window handles "at most" thresholds well: expand the right side, and when the constraint breaks, shrink from the left. "Exactly k" has no such clean shrink rule. A window below k distinct values needs to expand, a window above k needs to shrink, but when it sits at exactly k, there can be several valid subarrays ending at the same right pointer with different left boundaries, so counting one and moving on is wrong.

The standard transformation is exactly(k) = atMost(k) - atMost(k-1). Count subarrays with at most k distinct integers, subtract the count with at most k-1 distinct integers, and the difference is the count with exactly k distinct integers. "At most k" is a problem a single sliding window solves cleanly.

Key Constraints:

Intuition

Check every possible subarray. For each pair of indices (i, j) where i <= j, count the distinct integers in nums[i..j] and increment the answer if that count equals k.

Distinct integers can be tracked with a frequency map whose size gives the distinct count. Rather than rebuild the map for each (i, j) pair, fix the start index i and extend the end index j one element at a time, updating the same map. That keeps the inner work O(1) per step and brings the total from O(n^3) down to O(n^2).

Algorithm

Visualization and Code

For each starting index, the inner loop scans every ending index, up to 400 million iterations at the maximum n. The next approach reuses window state across positions instead of restarting from each index.

Intuition

Counting subarrays with at most k distinct integers fits a single sliding window. Maintain a window [left, right]. When the distinct count exceeds k, shrink from the left until it drops back to k. At each position of right, the number of valid subarrays ending at right is (right - left + 1), since every start index from left to right produces a window with at most k distinct values.

The decomposition exactly(k) = atMost(k) - atMost(k-1) then gives the answer directly. Every subarray counted in atMost(k) has either exactly k distinct values or fewer. Subtracting atMost(k-1) removes those with fewer than k, leaving only the ones with exactly k. One helper function, atMost(k), called twice.

Algorithm

Visualization and Code

This approach makes two full passes over the array. The next approach collapses them into one pass by tracking two left pointers at the same time.

Intuition

The subtraction approach computes atMost(k) and atMost(k-1) in separate passes. Both quantities can be tracked together, in a single pass, using two left pointers sharing one right pointer.

For a fixed right endpoint, let left1 be the smallest index where [left1, right] has at most k distinct values, and left2 the smallest index where [left2, right] has at most k-1 distinct values. The number of subarrays ending at right with exactly k distinct values is then left2 - left1: every start index from left1 to left2 - 1 produces a window with at most k distinct values but more than k-1, which is exactly k.

Both windows advance as right moves. The invariant left2 >= left1 always holds, since the stricter "at most k-1" constraint forces window 2's left edge to be at or ahead of window 1's.

Algorithm

Visualization and Code