-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSubarray With K diff Integers
More file actions
34 lines (34 loc) · 1.05 KB
/
Subarray With K diff Integers
File metadata and controls
34 lines (34 loc) · 1.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//output of this function -->numbers of subarrays which have number of different integers less than equal to k
int fun(int k,vector<int> nums)
{
if(k==0) return 0;
unordered_map<int,int> mp;
int j=0;
int count=0;
int n=nums.size();
int total=0;
vector<int> freq(n+1,0);
for(int i=0;i<n;i++)
{
if(freq[nums[i]]==0) count++;
freq[nums[i]]++;
if(count<=k) total+=(i-j+1); // (i-j+1) = number of subarrays ending at i-th position which contains number of different integers less than or equal to k
else
{
while(count>k)
{
freq[nums[j]]--;
if(freq[nums[j]]==0)
{
count--;
}
j++;
}
total+=(i-j+1);
}
}
return total;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return fun(k,nums)-fun(k-1,nums);
}