Using Map gave TLE but Priority Queue gave correct answer


#1

I can’t understand why using a map(with value and frequency) gave TLE (with correct answer, though) but using a priority queue did not. Isn’t complexity for basic operations in both log n? Then how did priority queue pass the time complexity test while map did not ?


#2

I’m also facing the same issue


#3

I am using map in the code below and it is working perfectly

int Solution::nchoc(int B, vector &A) {
if(A.size()==0)
return 0;
map<long long int,long long int> mp;
int i;
for(i=0;i<A.size();i++)
{
if(mp.find(A[i])==mp.end())
{
mp[A[i]]=1;
}
else
mp[A[i]]++;
}
int count=0;
map<long long int,long long int>::reverse_iterator it=mp.rbegin();
for(i=1;i<=B && !mp.empty();i++)
{
it=mp.rbegin();
long long int val=it->first;
count=(count+val)%1000000007;
if(it->second==1)
mp.erase(val);
else
it->second-=1;
if(val/2!=0)
{
if(mp.find(val/2)==mp.end())
mp[val/2]=1;
else
mp[val/2]++;
}
}
return count%1000000007;
}


#4

use crbegin() instead of rbegin() .