Subarrays with K Different Integers

1. Define the problem

Subarrays with K Different Integers

Given nums and k, count contiguous subarrays with exactly k different integers . Use exactly(k) = atMost(k) − atMost(k − 1), where atMost slides a window that never exceeds k distinct values.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums_i, k ≤ nums.length

Example

Inputnums = [1,2,1,2,3], k = 2

Output7

Explanation Subarrays: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

2. Know the words first

In plain terms

Subarray: A run of elements taken right out of the array as-is, next to each other in order — not values picked out from anywhere in the array.

3. Visualize the solution

atMost(2) − atMost(1) = exactly 2

StatusatMost(2)

r=0: window [1] contributes 1 → count = 1.

What happens in this step

window = [0, 0] = [1]
freq{1:1}, distinct=1 <= k(2)

count += (0-0+1) = 1 → count = 1

Step 1 of 4

Steps to visualize

Run atMost(k): grow right while the window has at most k distinct values.
When a (k+1)th distinct appears, shrink left until distinct ≤ k again.
Add (right − left + 1) to the count for every right — all valid endings.
Compute atMost(k − 1) the same way.
Exactly k equals atMost(k) minus atMost(k − 1).

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

atMost(2) − atMost(1) = exactly 2

StatusatMost(2)

r=0: window [1] contributes 1 → count = 1.

What happens in this step

window = [0, 0] = [1]
freq{1:1}, distinct=1 <= k(2)

count += (0-0+1) = 1 → count = 1

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function subarraysWithKDistinct(nums, k) {
  return atMost(nums, k) - atMost(nums, k - 1);
}

function atMost(nums, k) {
  if (k < 0) return 0;
  if (k === 0) return 0;

  const freq = new Map();
  let left = 0;
  let distinct = 0;
  let count = 0;

  for (let right = 0; right < nums.length; right++) {
    const v = nums[right];
    const prev = freq.get(v) ?? 0;
    if (prev === 0) distinct++;
    freq.set(v, prev + 1);

    while (distinct > k) {
      const lv = nums[left];
      const n = freq.get(lv) - 1;
      freq.set(lv, n);
      if (n === 0) distinct--;
      left++;
    }

    count += right - left + 1;
  }

  return count;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1,2,1,2,3], k = 2`	`7`	Docstring example
`nums = [1,2,1,3,4], k = 3`	`3`	LeetCode second example
`nums = [1], k = 1`	`1`	Single element array, k = 1
`nums = [1,1,1], k = 5`	`0`	k larger than distinct values present
`nums = [1,2,3], k = 3`	`1`	Entire array is the only valid subarray
`nums = [2,2,2], k = 1`	`6`	All identical values, k = 1
`nums = [1,2,3], k = 0`	`0`	k = 0 returns 0 defensively
`nums = [1,2,1,3,4,2,3,1,4,2], k = 3`	`9`	Larger hand-verified case
`nums = [1,1,2,3,2,1,4,5,1,2], k = 4`	`9`	Another larger hand-verified case

Subarrays with K Different Integers