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.
1#include <unordered_map>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int subarraysWithKDistinct(vector<int>& nums, int k) {
8 return atMost(nums, k) - atMost(nums, k - 1);
9 }
10
11private:
12 int atMost(vector<int>& nums, int k) {
13 unordered_map<int, int> count;
14 int left = 0, res = 0;
15 for (int right = 0; right < nums.size(); ++right) {
16 if (count[nums[right]]++ == 0) k--;
17 while (k < 0) {
18 if (--count[nums[left]] == 0) k++;
19 left++;
20 }
21 res += right - left + 1;
22 }
23 return res;
24 }
25};This C++ program solves the problem with a class Solution containing a method subarraysWithKDistinct. The helper function atMost calculates the number of subarrays with at most k distinct elements using an unordered_map to maintain a count and manage the sliding window efficiently.