All problems

Subarrays with K Different Integers

Hard · sliding window

You are given a list of whole numbers nums and a whole number k.

A subarray is a run of neighbouring entries of nums. Count the subarrays that contain exactly k different values. A value that appears several times in the subarray still counts once.

Subarrays are counted by position: two subarrays with the same values but at different places in nums are different subarrays, and each is counted.

Examples

Example 1

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

Output: 4

The subarrays are [3, 1], [1, 3], [3, 2] and [3, 1, 3]. The longer ones hold three different values.

Example 2

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

Output: 6

Every one of the six subarrays holds only the value 2.

Example 3

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

Output: 1

Only the whole list has three different values.

Constraints