992. Subarrays with K Different Integers

Link

Solution

Intuition:

First you may have feeling of using sliding window. Then this idea get stuck in the middle.

This problem will be a very typical sliding window, if it asks the number of subarrays with at most K distinct elements.

Just need one more step to reach the folloing equation: exactly(K) = atMost(K) - atMost(K-1)

Explanation

1. Write/copy a helper function of sliding window, to get the number of subarrays with at most K distinct elements.

2. Done.

Complexity:

Time O(N) for two passes. Space O(K) at most K elements in the counter

Java:

    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }
    int atMostK(int[] A, int K) {
        int i = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int j = 0; j < A.length; ++j) {
            if (count.getOrDefault(A[j], 0) == 0) K--;
            count.put(A[j], count.getOrDefault(A[j], 0) + 1);
            while (K < 0) {
                count.put(A[i], count.get(A[i]) - 1);
                if (count.get(A[i]) == 0) K++;
                i++;
            }
            res += j - i + 1;
        }
        return res;
    }