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;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
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>