Subarrays with K Different Integers

Problem

You are given an integer array nums and an integer k. Count the contiguous subarrays in which the number of distinct values is exactly k. Subarrays at different positions are counted separately even if their contents are identical.

• nums has between 1 and 20,000 elements; values are positive integers with no particular upper bound.
• k is between 1 and the length of nums.

Examples

• nums = [4, 7, 4, 7, 9], k = 2 → 7. They are [4,7], [7,4], [4,7], [7,9], [4,7,4], [7,4,7], [4,7,4,7].
• nums = [3, 6, 3, 8, 1], k = 3 → 3. [3,6,3,8], [6,3,8], [3,8,1].
• nums = [9, 9, 9], k = 1 → 6. Every subarray of a constant array has exactly one distinct value: 3 of length 1, 2 of length 2, 1 of length 3.

Hints

1. Try a window that keeps "exactly k distinct". Does shrinking a valid window always keep it valid? What goes wrong?
2. "At most k distinct" does shrink cleanly. How would you count subarrays satisfying that in one pass?
3. Answer = count(at most k) - count(at most k - 1). Each is a standard variable window where every right endpoint contributes hi - lo + 1 subarrays.