Subarrays with K Different Integers

Hard· variable window· at-most trick

Problem

Count the contiguous subarrays that contain exactly k distinct integers. Subarrays at different positions count separately even if they hold the same values.

Examples

Input: nums = [1,2,1,2,3], k = 2

Output: 7

For example [1,2], [2,1], [1,2,1] and [1,2,1,2] each have exactly two distinct values.

Input: nums = [1,2,1,3,4], k = 3

Output: 3

Constraints

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i], k <= nums.length

Hints & approach

Hint 1

"Exactly k" is awkward for a sliding window, but "at most k" is easy.

Hint 2

exactly(k) = atMost(k) - atMost(k - 1).

Hint 3

For atMost(k), every valid window ending at right contributes right - left + 1 subarrays.

Approachtry the hints first

Write a helper atMost(k) that slides a window with a value-count map: extend the right edge, and while the window has more than k distinct values, shrink from the left. For each right edge, all subarrays ending there and starting anywhere in [left, right] are valid, so add right - left + 1. The answer is atMost(k) - atMost(k - 1), which isolates subarrays with exactly k distinct values.

Time O(n) · Space O(n)

← PreviousMinimum Window Substring DoneBack to Sliding window