992. Subarrays with K Different Integers

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window (The Exactly K = AtMost(K) - AtMost(K-1) Trick)
• Hint: Counting subarrays with exactly K distinct elements directly is mathematically unstable with a single sliding window. Instead, write a helper for at most K, and subtract.
• Difficulty: Hard
• Companies: Google, Amazon, DoorDash, Adobe
• LeetCode: 992

Quick Sights

• Time Complexity: O(n). We run the atMost(k) sliding window helper twice. Each run takes $O(n)$ time because both pointers only move forward.
• Space Complexity: O(n) in the worst case (if all elements are distinct), or O(k) strictly, because our frequency map inside the helper never grows larger than k + 1 before shrinking.
• Core Mechanism: In a sliding window, tracking "exactly K" breaks because removing a duplicate from the left might not change the distinct count, making it ambiguous when to stop shrinking. Tracking "at most K" is monotonically safe. Therefore, the number of subarrays with exactly K distinct integers is strictly atMost(K) - atMost(K-1).

Concept Explanation

As a senior engineer, the leap to solving this Hard problem is recognizing the flaw in the standard sliding window.

A standard sliding window asks: "Is my window valid right now?" If you try to maintain a window with exactly 2 distinct elements (e.g., [1, 2, 1]), moving the left pointer past the first 1 leaves [2, 1]. The window still has exactly 2 distinct elements. This destroys the monotonic property sliding windows rely on, because you don't know if shrinking the window will make it invalid or keep it valid!

1. The Monotonic Fix: Change the constraint to "At Most K". If a window [1, 2, 1] has at most 2 distinct elements, then every subarray ending at the rightmost index ([1], [2, 1], [1, 2, 1]) also has at most 2 distinct elements.
2. Counting Combinatorics: If a valid window spans from left to right, it inherently contains exactly right - left + 1 valid subarrays that end at right.
3. The Math Trick: If you have a bag of subarrays with $\le K$ distinct elements, and you remove all the subarrays that have $\le K-1$ distinct elements, what is left? Only the subarrays with exactly $K$ distinct elements. $$\text{Exactly}(K) = \text{AtMost}(K) - \text{AtMost}(K-1)$$

Diagram

This flowchart illustrates the atMost(limit) helper function, which is called twice to solve the problem.

Study Pattern (SDE3+)

• 0–3 min: Do not attempt to explain a 3-pointer single-pass solution (it exists but is notoriously difficult to explain under pressure). Immediately jump to the AtMost(K) - AtMost(K-1) math trick. It is clean, modular, and proves strong foundational knowledge.
• Implementation pass: Write the atMost(limit) helper function first. Be extremely careful to delete keys from the frequency map when their count hits 0, otherwise map.size will be incorrect.
• 5 min extension: Discuss why the 3-pointer sliding window exists (to do it in one pass instead of two) and the trade-offs (micro-optimization vs code readability and maintainability).

Approaches

• Brute force — Generate all $O(n^2)$ subarrays, put them in a Set, check if size == K. Time: $O(n^3)$.
• One-Pass Sliding Window (3 Pointers) — Maintain one right pointer and two left pointers (left1 for at-most-K, left2 for at-most-K-1). Time: $O(n)$. Very hard to trace without bugs.
• Two-Pass Math Trick — Write a clean atMost helper. Call it twice. Time: $O(n)$. (Always pick this)

Optimal Solution

Go

func subarraysWithKDistinct(nums []int, k int) int {
	// Exactly K = (At Most K) - (At Most K-1)
	return atMostDistinct(nums, k) - atMostDistinct(nums, k-1)
}

func atMostDistinct(nums []int, limit int) int {
	if limit < 0 {
		return 0
	}
	
	counts := make(map[int]int)
	left := 0
	total := 0
	
	for right := 0; right < len(nums); right++ {
		counts[nums[right]]++
		
		// If we exceed the limit of distinct numbers, shrink from the left
		for len(counts) > limit {
			leftNum := nums[left]
			counts[leftNum]--
			
			// Critical: completely remove the key so len(counts) drops
			if counts[leftNum] == 0 {
				delete(counts, leftNum)
			}
			left++
		}
		
		// Every valid window [left, right] contains (right - left + 1) valid
		// subarrays that specifically end at the 'right' index.
		total += right - left + 1
	}
	
	return total
}

JavaScript

function subarraysWithKDistinct(nums, k) {
	// Exactly K = (At Most K) - (At Most K-1)
	return atMostDistinct(nums, k) - atMostDistinct(nums, k - 1);
}

function atMostDistinct(nums, limit) {
	if (limit < 0) return 0;
	
	const counts = new Map();
	let left = 0;
	let total = 0;
	
	for (let right = 0; right < nums.length; right++) {
		const num = nums[right];
		counts.set(num, (counts.get(num) || 0) + 1);
		
		// Shrink window if we have too many distinct integers
		while (counts.size > limit) {
			const leftNum = nums[left];
			counts.set(leftNum, counts.get(leftNum) - 1);
			
			// Critical: completely remove the key so counts.size drops
			if (counts.get(leftNum) === 0) {
				counts.delete(leftNum);
			}
			left++;
		}
		
		// Combinatorics: Add all valid subarrays ending at 'right'
		total += right - left + 1;
	}
	
	return total;
}

Walkthrough

Tracing atMostDistinct for nums = [1,2,1,2,3], limit = 2:

atMostDistinct(nums, 2) returns 11. atMostDistinct(nums, 1) returns 5. Exactly 2 = 11 - 5 = 6.

Output: 6

Edge Cases

• k == 0 (The LC problem guarantees $1 \le k \le nums.length$, but if $k=0$, the limit < 0 check safely catches the $k-1$ call and returns 0).
• k is larger than the total number of distinct integers in the entire array (Returns 0 because atMost(K) and atMost(K-1) will return the exact same maximum total).

Pitfalls

• Trying to compute "exactly K" using a single standard sliding window. You will almost certainly fail edge cases involving duplicate numbers at the edges of the window.
• Forgetting to physically delete the key from the Hash Map when the frequency drops to 0.

Similar Problems

• 904. Fruit Into Baskets — At most 2 distinct (Medium stepping stone). This is exactly the atMost(2) helper function, except it asks for max length rather than total count.
• 713. Subarray Product Less Than K — Another problem that relies on the exact same combinatorics trick (total += right - left + 1).

Mind-Map Tags

#sliding-window #exactly-k #at-most-trick #subarray-count #frequency-map #hard-classic