Problem Statement

Subarrays with K Different Integers

You are given a list of numbers called nums and a number k. A subarray is a slice of the list that is in one piece, with no gaps. For example, in [1,2,1,2,3] the slice [2,1,2] is a subarray, but [1,1,3] is not because you skipped over things. A subarray is "good" if it has exactly k different values inside it. The job is to count how many good subarrays there are. The hard part is the word "exactly." Counting "exactly k different values" while sliding a window is awkward, because a window does not snap cleanly to "exactly k." So we use a trick. It is easier to count subarrays with "at most k" different values, meaning k or fewer. And here is the key idea: the subarrays with exactly k different values are the ones with at most k, minus the ones with at most k-1. In short, exactly(k) = atMost(k) - atMost(k-1). The atMost helper uses a sliding window, which is much easier to write.

hardSliding WindowSliding WindowTime: O(n) · Space: O(n)

Signals to notice

count subarrays with exactly k distinct integersexact = atMost(k) - atMost(k-1)sliding window trick

Brute force first

Check every subarray — O(n²).

The key insight

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.

Trace it on `nums=[1,2,1,2,3], k=2 (answer = atMost(2) - atMost(1))`

atMost(2): r=0 v=1 -> count={1:1} size1, left=0, result+=1 => 1
atMost(2): r=1 v=2 -> {1:1,2:1} size2, left=0, result+=2 => 3; r=2 v=1 -> {1:2,2:1} size2, result+=3 => 6; r=3 v=2 -> {1:2,2:2} size2, result+=4 => 10
atMost(2): r=4 v=3 -> size3>2, shrink dropping 1,2,1 until left=3 {2:1,3:1} size2, result+=2 => 12. atMost(2)=12
atMost(1): r=0 v=1 -> {1:1}, result+=1 => 1; r=1 v=2 -> shrink to {2:1} left=1, result+=1 => 2
atMost(1): r=2 v=1 -> shrink to {1:1} left=2, +1 => 3; r=3 v=2 -> shrink to {2:1} left=3, +1 => 4; r=4 v=3 -> shrink to {3:1} left=4, +1 => 5. atMost(1)=5
answer = atMost(2) - atMost(1) = 12 - 5 = 7

What must stay true

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.

Shape of the loop

function subarraysWithKDistinct(nums, k):
  return atMost(k) - atMost(k - 1)

function atMost(k):
  left = 0; result = 0; count = {}        # map value -> freq in window
  for right in 0..n-1:
    count[nums[right]] += 1
    while size(count) > k:                 # too many distinct -> shrink
      count[nums[left]] -= 1; drop if 0; left += 1
    result += right - left + 1             # all windows ending at right
  return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying to directly count 'exactly k' with a single window — the window can grow and shrink unpredictably. The subtraction trick avoids this.

Sliding Window Pattern