992. Subarrays with K Different Integers

At a Glance

• Topic: sliding-window
• Pattern: Sliding Window (at-most trick)
• Difficulty: Hard
• Companies: Google, Amazon, DoorDash, Adobe
• Frequency: High
• LeetCode: 992

Problem (one-liner)

Given integer array numbers and integer targetDistinct, return the number of contiguous subarrays that contain exactly targetDistinct distinct values.

Recognition Cues

• "Exactly K distinct" in subarray
• Classic transform: exactly(K) = atMost(K) - atMost(K-1)
• Dual sliding window or two passes

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — enumerate every subarray and count distinct with a set — O(n³) time / O(k) space per check (acceptable only as sanity check).
• Better — two pointers attempting “exactly K” directly — sliding left while tracking distinct gets brittle when duplicates shift; often degrades to missed counts or O(n²).
• Acceptable (same asymptotic, clearer proof) — compute atMost(K) with one sliding window and reuse — O(n) time / O(n) space for the frequency map.
• Optimal — exactly(K) = atMost(K) − atMost(K−1) — two passes (or two calls), same bounds; pick this in interview because correctness is localized to the monotone atMost helper.

Optimal Solution

Go

func subarraysWithKDistinct(numbers []int, targetDistinct int) int {
	return atMostDistinct(numbers, targetDistinct) - atMostDistinct(numbers, targetDistinct-1)
}

func atMostDistinct(numbers []int, limit int) int {
	if limit < 0 {
		return 0
	}
	counts := make(map[int]int)
	leftPointer := 0
	total := 0
	for rightPointer := 0; rightPointer < len(numbers); rightPointer++ {
		counts[numbers[rightPointer]]++
		for len(counts) > limit {
			leftValue := numbers[leftPointer]
			counts[leftValue]--
			if counts[leftValue] == 0 {
				delete(counts, leftValue)
			}
			leftPointer++
		}
		// invariant: window [leftPointer..rightPointer] has <= limit distinct values
		total += rightPointer - leftPointer + 1
	}
	return total
}

JavaScript

function subarraysWithKDistinct(numbers, targetDistinct) {
	return (
		atMostDistinct(numbers, targetDistinct) -
		atMostDistinct(numbers, targetDistinct - 1)
	);
}

function atMostDistinct(numbers, limit) {
	if (limit < 0) {
		return 0;
	}
	const counts = new Map();
	let leftPointer = 0;
	let total = 0;
	for (let rightPointer = 0; rightPointer < numbers.length; rightPointer++) {
		const value = numbers[rightPointer];
		counts.set(value, (counts.get(value) || 0) + 1);
		while (counts.size > limit) {
			const leftValue = numbers[leftPointer];
			counts.set(leftValue, counts.get(leftValue) - 1);
			if (counts.get(leftValue) === 0) {
				counts.delete(leftValue);
			}
			leftPointer++;
		}
		total += rightPointer - leftPointer + 1;
	}
	return total;
}

Walkthrough

numbers = [1,2,1,2,3], targetDistinct = 2

• atMost(2) counts all subarrays with 1 or 2 distinct.
• atMost(1) counts subarrays with a single distinct.
• Subtract → subarrays with exactly 2 distinct.

Invariant: for fixed rightPointer, every leftPointer in [0..L] with window valid contributes rightPointer - leftPointer + 1 implicitly captured by summing rightPointer - leftPointer + 1 at each step.

Edge Cases

• targetDistinct == 0 — definition; LC expects 0 (empty subarray not counted)
• All elements identical — only K==1 works
• K > distinct values in whole array → 0

Pitfalls

• Implementing exactly K directly with one window — messy; at-most decomposition is standard
• Using map.size for distinct count — must delete keys when zero

Similar Problems

• 904. Fruit Into Baskets — at most 2 distinct (Medium stepping stone).
• 424. Longest Repeating Character Replacement — bounded window validity (Medium; different metric).
• 76. Minimum Window Substring — multiset constraint (Hard sibling).

Variants

• Longest subarray with exactly K distinct — maximize length instead of counting; still built from atMost(K) − atMost(K−1) on lengths (LeetCode 992’s cousin family).
• Many queries with different K on the same array — reuse preprocessing or Mo’s algorithm if offline range queries matter more than O(n) per query.
• Multiset values (not keys) — replace distinct-count with frequency histogram validity; atMost needs a different validity predicate.

Mind-Map Tags

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