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.
1import java.util.HashMap;
2
3public class Solution {
4 public int subarraysWithKDistinct(int[] nums, int k) {
5 return atMost(nums, k) - atMost(nums, k - 1);
6 }
7
8 private int atMost(int[] nums, int k) {
9 HashMap<Integer, Integer> count = new HashMap<>();
10 int left = 0, res = 0;
11 for (int right = 0; right < nums.length; right++) {
12 count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
13 if (count.get(nums[right]) == 1) k--;
14 while (k < 0) {
15 count.put(nums[left], count.get(nums[left]) - 1);
16 if (count.get(nums[left]) == 0) k++;
17 left++;
18 }
19 res += right - left + 1;
20 }
21 return res;
22 }
23}This Java program makes use of two functions, subarraysWithKDistinct and atMost. The atMost function utilizes a HashMap to track the count of each number. It calculates the number of subarrays with at most k distinct numbers, which helps in finding the exact subarray count with k distinct integers by difference.