top k frequent elements// T.C O(nlogk) using priority queue
Bhumika_2808
100
Heap (Priority Queue)Interview

T.C of O(nlogk) using priority queue ,easy to understand

class Solution {
public:
vector topKFrequent(vector& nums, int k) {
//t.c o(nlogk) as we are pushing only k most frequent elements in pq(min heap)
//s.c o(n+k)
vector res;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
map<int,int> mp; //for storing occurrences of every element in nums

    for(int i=0;i<nums.size();i++)
    {
       mp[nums[i]]++;
    }
    
    for(auto x:mp) //storing top k most frequent elements 
    {
        if(pq.size()<k) pq.push({x.second,x.first});
        else if( pq.top().first<x.second)
        {
            pq.pop();
            pq.push({x.second,x.first}); //{occurrence,element}
        }
    }
   while(!pq.empty())
    {
        res.push_back(pq.top().second);
        pq.pop();
    }
    
    return res;
}

};

Comments (0)