Subarrays with K Different Integers

Share

Count number of subarrays with exactly K different integers.

Example 1
Input: nums=[1,2,1,2,3], k=2 → Output: 7
Example 2
Input: nums=[1,2,1,3,4], k=3 → Output: 3

Solution Approach

Use atMost(k) - atMost(k-1). atMost counts subarrays with at most K distinct.

  • Implement atMost(k): sliding window with freq map
  • Shrink left when distinct > k
  • Count subarrays ending at right: right-left+1
  • Return atMost(k) - atMost(k-1)
Java
public int subarraysWithKDistinct(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    int left = 0, count = 0;
    for (int right = 0; right < nums.length; right++) {
        freq.merge(nums[right], 1, Integer::sum);
        while (freq.size() > k) {
            freq.merge(nums[left], -1, Integer::sum);
            if (freq.get(nums[left]) == 0) freq.remove(nums[left]);
            left++;
        }
        count += right - left + 1;
    }
    return count;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)