02
Top K by frequency (Heap — Top K Sub-pattern)
The rank is how often an item appears. Count first with a hash map, then pick the K best counts with a heap (or bucket by count).
Signals in the problem statement
- ›
"k most frequent elements / words"
- ›
"sort characters by how often they appear"
What makes it different
Top K Frequent Elements is the template; buckets make it O(N). Sort Characters by Frequency outputs every character, so it's "sort by count", and characters with equal counts must stay grouped ("aabb", never "abab"). Top K Frequent Words adds a tie rule: equal counts → the alphabetically smaller word ranks higher. So the size-K heap must evict the larger word on a tie, and the output is reversed at the end.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Top K Frequent ElementsWalkthroughMediumBasic Anchor·LeetCode #347
- 2Sort Characters By FrequencyWalkthroughMediumBasic Reinforcement·LeetCode #451
- 3Top K Frequent WordsWalkthroughMediumSlight Variation·LeetCode #692
Template
top-k-frequent-template.cpp
// Top k frequent: count first, then a size-k min-heap keyed on the COUNT.
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // (count, value)
for (auto& [v, c] : cnt) {
pq.push({c, v});
if ((int)pq.size() > k) pq.pop(); // drop the least frequent
}
vector<int> out;
while (!pq.empty()) { out.push_back(pq.top().second); pq.pop(); }
return out; // least -> most frequent
}Remember this · Heap — Top K
Trigger
"K largest / smallest / most frequent / closest", kth element, streaming top-K.
Think
Do I really need everything sorted, or only the best K?
Key question
Min-heap or max-heap of size K — which one lets me kick out the worst candidate?