 # Simplify editorial !!

Can any one explain given editorial or another method to solve this problem

## Problem

Find the number of subarrays that have same number of distinct elements as the number of distinct elements in the whole array A[1, N].

## Solution

Let L = 1, R = 1, and number of distinct elements in the original array be K <= N.

Maintain a map to count the frequency of the elements, and a set to count the number of distinct elements in the current subarray.

STEP1:

Increment R until the number of distinct elements in range [L = 1, R] equal to K, let this R be R1 <= N. Now since the subarray [L = 1, R1] has K distinct elements, so all the subarrays starting at L = 1 and ending after R1 will also have K distinct elements. Thus add N-R1+1 to the answer.

STEP2:

Now keeping R same, increment L. Now, the subarray is [L = 2, R = R1].
Decrease the frequency of the previous element ie. A, and if its frequency = 0, remove it from the set. Repeat the STEP1.

## Pseudocode

``````A = [1, N] // given array

map <int,int> M
set <int> S

R = 1, ans = 0, K = no. of dist. elements

for L = 1 to N:
while R smaller than or equal to N and SIZE(S) smaller than K:
M[A[R]] += 1
S.insert(A[R])
R += 1

if SIZE(S) == K:
ans += N-R+1
M[A[L]] =- 1
if M[A[L]] == 0:
S.remove(A[L])

PRINT(ans)``````
2 Likes

@c_utkarsh In last lines, it should be M[A[L]]-=1 and if (M[A[L]]==0) s.remove(A[L]). isn’t it ?

1 Like

Yes, thanks for pointing it out. Updated now.

thanks but problem is i dont know c++ (so the concept of set,map) , how can i solve using c lang

checking for all subsets will give TLE O(n^3) ,so how to do in O(n) steps.
P.S:- dont know c++

is there no way to solve without map,vector plz help me out. I have tried really hard :’( plz -/-

To do this without map/set, you can put all elements into another array, sort that array, then keep the frequency table of size n as an array instead of a map. Now you can perform sliding window mentioned above. To update frequency table, you you can binary search the index of A[L] from the other sorted array.

Well, future suggestion just use C++. Most C code will work with a C++ compiler anyway 3 Likes

As @hikarico mentioned, you can solve this in C as well, the idea remains the same but the implementation will be more complex. You can refer to following C submission for a different implementation.

https://www.hackerearth.com/submission/7854882/

I would recommend you to learn C++ as its Standard Template Library (STL) is very useful in competitive programming.

1 Like

Im not getting why we need frquency array?

We need frequency array/map because if frequency of an element becomes 0 in the subarray, the number of distinct elements in it decreases by 1.

@c_utkarsh for frequency array its size should be 10^9 ,bcoz value of array
ranges from 1 to 10^9. This much size is not allowed, so how to keep track of frquency of a no. (upto 10^9)

@hikarico i have used ur logic it gives run time error(SIGSEGV) for half test cases
solution :- https://www.hackerearth.com/submission/9085937/

@code_man that’s why you need the binary search part. While traversing through the sorted array from left,binary search the element at the cuurent_index in the left subarray (from starting index to current-1 index). In binary search, find the index of the rightmost occurrence of the current element.

Once you find the index, in your frequency array “f”,
f[current_inde]=f[found_index]+1; (Here I am thinking your frequency array is initialised to zero initially and you will correctly handle the case when the element is found in the left subarray).

O(n) space- frequency updation.

1 Like

can u plz code it in c ,im not understanding from ur code ill dry run with paper pen. literally causing me headache and frustation, u can understand by how long discussion is going on

@code_man look at this pseudo-code.

``````// replace var's accordingly
int bs(int k,int beg,int end){
if(beg>end)
return(0);
int mid=(beg+end)/2;
if(a[mid]==k&&!(a[mid+1]==k&&mid+1<=a.size()))
return(mid);
else if(a[mid]==k)
return(bs(a,k,mid+1,end));
else if(a[mid]>k)
return(bs(a,k,beg,mid-1));
else
return(bs(a,k,mid+1,end));
}
int main(){
// following 1 based indexing
// frequency=0;
// "a" sorted array
for(i=1;i<=n;i++){
frequency[i]=frequency[bs(a[i],1,i-1)]+1;
}
}

Hope it helps!!``````

Above mentioned frequency array finds frequency of elements considering entire sorted array, but algorithm mentioned requires to find frequency of elements of subarray(from L to R-1,which is original unsorted array). So that for each element in these sub array till distinct count equals k in subarray.
So how we will find frequency of elements in given subarray of original array(not sorted) plz help me

@code_man when you want to do as described by @c_utkarsh, M[A[L]]-=1; then you have to binary search the rightmost occurrence of A[L] in sorted array “a” (considering original array- A and sorted -a).And take the frequency value at the searched index and do whatever you want.

I got accepted all test cases except last , where n= 200000 and all its element are same.

my solution :- https://www.hackerearth.com/submission/9127577/

I dont know why it failed to store (200000*200001)/2. I have declared it as unsigned long long count.(same as others who got these test case accepted)
plz last time last case help me plzz

//