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 exactlyK.

(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:

1 2 3 4 5 6 7

Input: A = [1,2,1,2,3], K = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Input: A = [1,2,1,3,4], K = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Analysis

Brute-Force

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

publicintsubarraysWithKDistinct(int[] A, int K) { intn= A.length; intcount=0; for (inti=0; i < n; ++i) { for (intj= i; j < n; ++j) { intsubLen= j - i + 1; if (subLen < K) continue; // length does not respect Set<Integer> set = newHashSet<>(); for (intt= i; t <= j; ++t) { // for each element in subarray set.add(A[t]); } if (set.size() == K) ++count; } } return count; }

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.

publicintsubarraysWithKDistinct(int[] A, int K) { intn= A.length; intcount=0; for (inti=0; i < n; ++i) { Set<Integer> set = newHashSet<>(); intj= i; while (j < n && set.size() < K) { set.add(A[j]); ++j; } // set's size equals K or j >= n if (set.size() == K) { ++count; while (j < n) { // keep adding to the set set.add(A[j]); if (set.size() == K) { ++count; ++j; } else { break; } } } } return count; }

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]: