C++ 19ms Priority queue pair solution

  • 1

    Here is my solution. But I think the runtime is O(klog(n)). Because I popped the priority queue k times. Each pop of a priority queue take log(n). Is that right?

    class Solution {
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> map; // value -> frequency
            priority_queue< pair<int,int> > q; // /frequency -> value ; max priority queue
            for(int x : nums) { // record the frequency in the map
            vector<int> output;
            for(auto x : map){
                q.push(make_pair(x.second, x.first)); // reverse key and value pair
            while(q.size() && k){ 
                output.push_back(q.top().second); // queue: frequency -> value
            return output;

  • 0

    Thanks for the solution! I tend to forget about priority queues. I'm glad you've reminded me :-)

    Yes, the O(log(n)) look up time is correct. However the code is a pure N log(N) because of the map.size() inserts into the queue :(.

    I think this could be changed by using one of the range constructors for the priority_queue and supplying an explicit compare function instead of reversing the pair values. In that case it would be an O(N) construction cost -- basically the cost of making a heap.

    Here is a version:

        vector<int> topKFrequent_next(vector<int> nums, int k) {
            unordered_map<int, int> freqs;
            for (auto num : nums)
            // shorthand
            using elt = pair<int, int>;
            auto cmp = [](elt lhs, elt rhs)
            { return lhs.second < rhs.second; };
            // See http://en.cppreference.com/w/cpp/container/priority_queue/priority_queue
            priority_queue<elt, vector<elt>, decltype(cmp)> queue(begin(freqs), end(freqs), cmp);
            vector<int> res(k);
            for (int i = 0; i < k; ++i) {
                res[i] = queue.top().first;
            return res;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.