Solution


Approach 1: Sliding Window

Intuition

For convenience, let's denote subarrays by tuples: (i,j) = [A[i], A[i+1], ..., A[j]], and call a subarray valid if it has K different integers.

For each j, let's consider the set of all i such that the subarray (i, j) is valid.

Firstly, must be a contiguous interval. If i1 < i2 < i3, (i1,j) and (i3,j) are valid, but (i2,j) is not valid, this is a contradiction because (i2,j) must contain more than K different elements [as (i3,j) contains K], but (i1,j) [which is a superset of (i2,j)] only contains K different integers.

So now let's write as intervals: .

The second observation is that the endpoints of these intervals must be monotone increeasing - namely, and are monotone increasing. With similar logic to the above, we could construct a proof of this fact, but the intuition is that after adding an extra element to our subarrays, they are already valid, or we need to shrink them a bit to keep them valid.

Algorithm

We'll maintain two sliding windows, corresponding to and . Each sliding window will be able to count how many different elements there are in the window, and add and remove elements in a queue-like fashion.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Analysis written by: @awice.