Subarrays with K Different Integers

Problem Return the number of contiguous subarrays containing exactly k distinct integers.

Input / Output

• Input: int array nums, int k. Output: count of subarrays.

Constraints

• n up to 2*10^4; O(n) expected — direct exact-k windowing is awkward, which is the trap.

Example

• nums = [1,2,1,2,3], k = 2 → 7; nums = [1,2,1,3,4], k = 3 → 3.

Expected approach

• exactly(k) = atMost(k) − atMost(k−1), where atMost(K) counts subarrays with ≤ K distinct via a standard shrinking window: each valid window ending at r contributes (r − l + 1). Two linear passes → O(n) time, O(k) space. Explaining WHY exact-k can't be windowed directly (validity isn't monotone in window size) and the alternative three-pointer/two-window technique earns the senior signal.