You are given an array A of size n. Each element of the array is a positive number.
A subarray is defined by (i,j) is called a good-subarray if the number of distinct elements in (A[i], A[i+1], \cdots, A[j] is not greater than B.
You are asked to tell the number of good-subarrays of each length 1 to n for the given array.
Input Format
The first argument is the array A
The second argument denotes the value B
Output Fromat
Return an array of integers where i^{th} integer denotes the number of good-subarrays of length (i+1)
Constraints 1 \leq n, A[i] \leq 10^5 1 \leq B \leq n
For Example
Input 1 : A = [1, 2, 2, 3, 1] B = 2
Output 1 : 5\,4\,2\,0\,0
Explanation :
For length 1 : [1], [2], [2], [3], [1]\rightarrow count = 5
For length 2 : [1,2], [2,2], [2,3], [3,1] \rightarrow count 4
For length 3: [1,2,2], [2,2,3] \rightarrow count = 2
For length 4 : \rightarrow count = 0
For length 5 : \rightarrow count = 0
You base the code on the fact that the answer is the sum of length of longest subarrays with sum less than B.
int ans=0;
for(int i=0; i<n; i++) { // for all i
int sum=0;
int j=i;
while(j<n && sum+a[j]<B) // find the longest subarray
sum+=a[j++];
ans+=(j-i); // count up its length
}
cout<<ans<<endl;
The code above (not tested, just typed it) has two nested loops, so in runs in O(n^2).
If this is not fast enough you can implement some sliding window, or two pointer, something like this:
int ans=0;
int l=0;
int r=0;
int sum=0;
while(sum+a[r]<B)
sum+=a[r++];
for(int l=0; l<n; l++) {
if(l>0)
sum-=a[l];
l++;
while(r<n && sum+a[r]<B)
sum+=a[r++];
ans+=(r-l);
}
Two pointer because you have two indexes, a left and a right one.
Sorry I didn’t get it. I couldn’t relate it with my question that how does it answers my question. In the question it is given that you have to count all those sub arrays who have count of their distinct elements not greater than B and here I think you are calculating the sum.
Ah… sorry, I did get the question wrong.
But the principle is the same.
For every i, find the number of good subarrays starting at i. Add their counts.
Since B is not the sum of elements in this subarrays, but the distinct count of elements, you can use a multimap to count them. some documentation
