0992.md

992. Subarrays with K Different Integers

Level:

Topic:

Similar Problem:

• 1248. Count Number of Nice Subarrays

Question

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

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

Input: nums = [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]

Intuition

Same as 1248

Code

Time: O(n)
Space: O(k)

public int subarraysWithKDistinct(int[] nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k-1);
}


private int atMostK(int [] nums, int k) {
    HashMap<Integer, Integer> window = new HashMap<>();

    int ans = 0;
    int left = 0, right = 0;
    while (right < nums.length) {
        int n = nums[right];
        right++;

        window.put(n, window.getOrDefault(n, 0)+1);
        while (window.size() > k) {
            n = nums[left++];
            window.put(n, window.get(n)-1);
            if (window.get(n) == 0)
                window.remove(n);
        }

        ans += right-left;
    }
    return ans;
}