C++: Top K Frequent Elements

Thought Process

To find the Top K frequent elements, we need an efficient approach to count and prioritize frequencies. First, we use a hash map to count frequencies of each element. Then, we use a min heap to dynamically track the K most frequent elements, removing smaller frequencies as we iterate. Finally, we extract the result from the heap. 

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        typedef pair<int,int> pi;
        priority_queue<pi,vector<pi>,greater<pi>> pq; // Min Heap
        vector<int> ans;

        // Store the frequency of each element.
        unordered_map<int,int> mp;
        for(int x : nums){
            mp[x]++;
        }

        // Every element inside a map is a pair
        for(auto entity : mp){

            pq.push({entity.second,entity.first});

            // All smaller frequency element will pop out.
            if(pq.size()>k)
                pq.pop();
        }

        while(!pq.empty()){

            int x = pq.top().second;
            ans.push_back(x);
            pq.pop();
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n log k)

Building the frequency map takes O(n) time, and heap operations take O(n log k) as we maintain at most k elements.

Space Complexity: O(n)

We use extra space for the frequency map and priority queue, both proportional to the input size.

Code copied!