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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int atMost(int* nums, int numsSize, int k) {
6 int* count = (int*)calloc(numsSize + 1, sizeof(int));
7 int left = 0, right = 0, result = 0;
8 for (; right < numsSize; ++right) {
9 if (count[nums[right]]++ == 0) k--;
10 while (k < 0) {
11 if (--count[nums[left]] == 0) k++;
12 left++;
13 }
14 result += right - left + 1;
15 }
16 free(count);
17 return result;
18}
19
20int subarraysWithKDistinct(int* nums, int numsSize, int k) {
21 return atMost(nums, numsSize, k) - atMost(nums, numsSize, k - 1);
22}The C implementation employs a dynamic array for counting the frequency of numbers in the current sliding window, facilitating the calculation of subarrays at most k distinct numbers.