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.
1def subarraysWithKDistinct(nums, k):
2 def atMost(k):
3 from collections import Counter
4 count = Counter()
5 left = 0
6 res = 0
7 for right in range(len(nums)):
8 if count[nums[right]] == 0:
9 k -= 1
10 count[nums[right]] += 1
11 while k < 0:
12 count[nums[left]] -= 1
13 if count[nums[left]] == 0:
14 k += 1
15 left += 1
16 res += right - left + 1
17 return res
18
19 return atMost(k) - atMost(k - 1)This Python function calculates the number of subarrays with exactly k distinct integers. The function atMost(k) helps in calculating the number of subarrays with at most k distinct integers using a sliding window technique.
We then utilize this function to find the result by calculating atMost(k) - atMost(k - 1), which gives us the count of subarrays with exactly k distinct numbers.