 # Good-SubArrays Problem (Past Contest)

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 : , , , ,  \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

How to solve this problem? Kindly help.

For any start index i find the length of the longest possible sub array with sum less than B.

For finding the longest possible sub arrays at any index use some technique like this: https://www.geeksforgeeks.org/window-sliding-technique/

@spookywooky Bro can you please explain with example it will make it more clear … 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.