Reference: LeetCode
Difficulty: Hard

## Problem

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Note:

• The resulting subarrays is not required to be distinct.
• 1 <= A.length <= 20000
• 1 <= A[i] <= A.length
• 11 <= K <= A.length

Example:

## Analysis

### Brute-Force

For each subarray ($\sim N^2$ in total), check if there are K distinct elements.

Time: $O(N^3)$
Space: $O(N)$

### Hash Set

For each element A[i] as the starting element of a subarray, we can use a hash set to control the current number of elements. Specifically, we first keep adding elements to the set until its size reaches K or there are no more elements that could be added.

Time: $O(N^2)$
Space: $O(K)$ since the size of the set is limited by $K$.

### Sliding Window

The idea is to calculate the number of subarrays with at most K distinct characters and with at most K - 1 distinct characters and then do subtraction.

Example of calculating the count of at most K = 3 in [1, 2, 1, 3, 4]:

Notice why count += end - start + 1 works here.

Or in one-pass:

Time: $O(N)$
Space: $O(K)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.