712195. Subarrays with K Distinct Integers
Medium
Subarrays with K Distinct Integers
Summary
Given an array arr and an integer k, find the number of subarrays that contain exactly k distinct integers. This problem involves sliding window, arrays, data structures, and algorithms.
Detailed Explanation
The idea is to use a sliding window approach to count the number of subarrays with k distinct integers. Initialize two pointers, start and end, to the beginning of the array. Initialize an empty set distinct to store unique elements in the current window.
- Expand the window by moving the
endpointer to the right. - For each new element encountered, update the
distinctset accordingly (add or remove as necessary). - Count the number of subarrays with exactly
kdistinct integers within the current window. - Shrink the window by moving the
startpointer to the right when the size ofdistinctexceedsk. - Repeat steps 1-4 until the end of the array is reached.
Time Complexity: O(n)
Space Complexity: O(min(k, n)) where n is the length of the array
Optimized Solutions
Java
import java.util.*;
public class Main {
public static int subarraysWithKDistinct(int[] arr, int k) {
Map<Integer, Integer> distinctCount = new HashMap<>();
int start = 0;
int end = 0;
int count = 0;
while (end < arr.length) {
if (!distinctCount.containsKey(arr[end])) {
distinctCount.put(arr[end], 1);
} else {
distinctCount.put(arr[end], distinctCount.get(arr[end]) + 1);
}
while (distinctCount.size() > k && start <= end) {
if (distinctCount.get(arr[start]) == 1) {
distinctCount.remove(arr[start]);
} else {
distinctCount.put(arr[start], distinctCount.get(arr[start]) - 1);
}
start++;
}
count += end - start + 1;
end++;
}
return count;
}
}