Count number of subarrays with exactly K different integers.
Input: nums=[1,2,1,2,3], k=2 → Output: 7
Input: nums=[1,2,1,3,4], k=3 → Output: 3
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)
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)