Sponsored
Sponsored
The two-pointer technique can be employed with a sliding window approach to count subarrays with exactly k distinct numbers. The key idea is to maintain a window using two pointers that expand and shrink to keep track of the number of unique integers.
For this, we use the number of subarrays with at most k distinct numbers and at most (k-1) distinct numbers. The difference between these two values gives the number of subarrays with exactly k distinct integers.
Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice.
Space Complexity: O(n), due to the storage used by the hash map.
1function subarraysWithKDistinct(nums, k) {
2 return atMost(nums, k) - atMost(nums, k - 1);
3}
4
5function atMost(nums, k) {
6 const count = new Map();
7 let left = 0, result = 0;
8 for (let right = 0; right < nums.length; right++) {
9 if (!count.has(nums[right])) k--;
10 count.set(nums[right], (count.get(nums[right]) || 0) + 1);
11 while (k < 0) {
12 count.set(nums[left], count.get(nums[left]) - 1);
13 if (count.get(nums[left]) === 0) {
14 count.delete(nums[left]);
15 k++;
16 }
17 left++;
18 }
19 result += right - left + 1;
20 }
21 return result;
22}The JavaScript solution uses two functions: subarraysWithKDistinct and atMost. The latter function computes at most k distinct integers using a map for counting and managing a sliding window.