We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Used the simple idea that search in keys of map takes O(1) time and search in values of map takes O(n) time.

first map will store <element, frequency>second map will store <frequency, frequencyCount>

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(0);intnq;cin>>nq;// first will contain <element, frequency> pairsmap<int,int>first;// second will contain <frequency, frequencyCount> pairsmap<int,int>second;for(inti=0;i<nq;i++){inta,b;cin>>a>>b;if(a==1){// Insert b into first map.// Update the frequencies in second map.intelem=first[b];// ele = current frequency of element b.if(elem>0){// b was already present.second[elem]--;}// Add b // increase frequency of bfirst[b]++;// Update the count of new frequency in second mapsecond[first[b]]++;}elseif(a==2){// Remove binttemp=first[b];// temp = current frequency of element bif(temp>0){// b is presentsecond[temp]--;// Update frequency countfirst[b]--;// decrease element frequencysecond[first[b]]++;// Update frequency count}}else{// check for the b frequency of any elementintres=second[b];if(res>0){cout<<1<<endl;}else{cout<<0<<endl;}}}return0;}

we just needed to store frequencies of elements in such a way that we can perform search efficiently. So, to store them in keys, just storing their frequency count (frequency of frequencies) in values. so, frequency count is just used to store the actual element frequencies in keys.

I ended up creating a frequancy dictionary to store the frequancy as a key, and a Hash Set of values. I did this because the key needs to be unique, and in most cases, using a frequancy dictionary of integers alone would fail.

If you follow this path, always remember to remove the value from the current frequancy hash set before you move it onto the next, whenever you add or subtract. Don't worry about removing the entry, if there are no more values in a certain frequencies Hash Set. Just check that the Hash Set has a Count greater than 0, when asserting that the frequancy can be found.

## Frequency Queries

You are viewing a single comment's thread. Return to all comments →

Used the simple idea that search in keys of map takes O(1) time and search in values of map takes O(n) time.

`first map will store <element, frequency>`

`second map will store <frequency, frequencyCount>`

Since query 2 only removes a single element at most, there's no need to use the

`temp`

variable.What is frequency count for?

we just needed to store frequencies of elements in such a way that we can perform search efficiently. So, to store them in keys, just storing their frequency count (frequency of frequencies) in values. so, frequency count is just used to store the actual element frequencies in keys.

Thank you. I figured it out!

I do not understand how you account for using frequancies as keys, given that keys have to be unique, and frequancies are not always unique.

I ended up creating a frequancy dictionary to store the frequancy as a key, and a

Hash Setof values. I did this because the key needs to beunique, and in most cases, using a frequancy dictionary of integers alone would fail.If you follow this path, always remember to remove the value from the current frequancy hash set before you move it onto the next, whenever you add or subtract. Don't worry about removing the entry, if there are no more values in a certain frequencies Hash Set. Just check that the Hash Set has a

`Count`

greater than`0`

, when asserting that the frequancy can be found.Whats the use of this line please make me understand

if(elem > 0) { // b was already present. second[elem]--; }

Try to dry run the algortihm with an example. You'll get the idea of how the program runs.

whats the use of this line please make me uinderstand

even with this solution case 10 doesn't pass, I did the same in c++14