Top K Frequent Words — Editorial

Opening the reading…

Intuitionwhy the heap keeps exactly the words that can survive

The answer depends on two ranking rules: a word with a larger frequency is better, and among equal frequencies the lexicographically smaller word is better. Counting occurrences first turns the input into one record per unique word, with enough information to compare every candidate against the current top k.

A min-heap is useful here when its top is not the best word, but the worst word currently kept. For each unique word, insert it and remove the heap top if the heap grows past k. The removed word is safe to discard because it is worse than every word still in the heap. At the end, the heap contains the answer, but its top-to-bottom removal order is the reverse of the required order.

Approachkeep the heap's top equal to the weakest retained candidate

Count every word in an unordered map, because the heap needs one frequency record per unique word rather than one record per occurrence.

Build a comparator that treats lower frequency as worse and, for equal frequencies, treats the lexicographically larger word as worse; this makes the weakest retained candidate reach the top of the min-heap.

Visit every frequency record and push its pair into the heap, because every unique word must get one chance to enter the top k.

If the heap size exceeds k, pop its top immediately, because that top is the weakest candidate and allowing more than k records would make later decisions compare against discarded words indirectly.

Create an output vector of size k and remove heap elements from weakest to strongest, placing each removed word from right to left so the final vector is ordered from strongest to weakest.

Return the filled vector without sorting it again, because the extraction positions already account for both ranking rules.

Complexitycounting, retaining, and producing the ordered result

MEASURE	BOUND	WHY
Time	Expected O(n + m log k)	Counting touches each of the n input words once. Each of the m unique words enters a heap of size at most k, so one insertion and, when needed, one removal cost O(log k); the final k removals cost O(k log k), which is included because k is at most m.
Space	O(m + k) extra	The frequency map stores m records and the heap stores at most k records. The returned vector has k strings, but required output storage is excluded from the extra-space bound. Since m and k can both be O(n) in the worst shape of input, the bound degrades to O(n).

Here n is the number of input words, m is the number of unique words, and k is the requested result size.

Annotated solutionC++ · hash map plus bounded min-heap · complete judge-ready solution

CPPCount frequencies, keep the weakest of the current top k at the heap top, and extract into the result from right to left.

#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for (const string& word : words) {
            ++freq[word];
        }

        auto cmp = [](const pair<int, string>& a,
                      const pair<int, string>& b) {
            return a.first > b.first ||
                   (a.first == b.first && a.second < b.second);
        };

        priority_queue<pair<int, string>,
                       vector<pair<int, string>>,
                       decltype(cmp)> pq(cmp);

        for (const auto& entry : freq) {
            pq.push({entry.second, entry.first});
            if (static_cast<int>(pq.size()) > k) {
                pq.pop();
            }
        }

        vector<string> answer(k);
        for (int i = k - 1; i >= 0; --i) {
            answer[i] = pq.top().second;
            pq.pop();
        }

        return answer;
    }
};

The comparator is the central placement decision. For different frequencies, the smaller frequency is made weaker. For equal frequencies, the lexicographically larger word is made weaker. Therefore pq.top() is exactly the record to remove when the heap has k + 1 elements. The unordered map's iteration order does not matter because every record is judged by the comparator before it can affect the retained set.

Sorting all unique words is simpler, but gives up the bounded heapa different arrangement, not an optimization

A competent alternative is to copy the frequency records into a vector and sort the entire vector by descending frequency, then ascending word. This is easier to read because the comparator directly describes the required final order. It is not an optimization: sorting all m records costs O(m log m), while the heap only maintains k records and costs O(m log k).

CPPAlternative full sort: order every unique word directly, then take the first k records.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for (const string& word : words) {
            ++freq[word];
        }

        vector<pair<int, string>> entries;
        entries.reserve(freq.size());
        for (const auto& entry : freq) {
            entries.push_back({entry.second, entry.first});
        }

        sort(entries.begin(), entries.end(),
             [](const pair<int, string>& a,
                const pair<int, string>& b) {
                 if (a.first != b.first) {
                     return a.first > b.first;
                 }
                 return a.second < b.second;
             });

        vector<string> answer;
        answer.reserve(k);
        for (int i = 0; i < k; ++i) {
            answer.push_back(entries[i].second);
        }
        return answer;
    }
};