#692
Top K Frequent Words
Medium Heap with a two-key comparator
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the k most frequent words, sorted by frequency (high to low) and alphabetically for ties.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k most frequent words, ties in alphabetical order.
Why this works: a min-heap of size k where the "worst" word sits on top (lower count, or later alphabetically). Reverse at the end.
Example: ["i","love","leetcode","i","love","coding"], k = 2
i:2, love:2, others 1tie → "i" before "love" → ["i", "love"]
✦Hints open one at a time
Count with a HashMap.
Keep a min-heap of size k where the "worst" word is on top: lower frequency, or alphabetically later on ties.
Pull the heap out and reverse it at the end.
↗Approach
Comparator for the min-heap: frequency ascending, then word descending. Keep size k. Poll everything into a list and reverse.
</>Solution (Java)
import java.util.*;
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
int fa = freq.get(a), fb = freq.get(b);
if (fa != fb) return Integer.compare(fa, fb); // less frequent = worse
return b.compareTo(a); // later in alphabet = worse
});
for (String w : freq.keySet()) {
heap.offer(w);
if (heap.size() > k) heap.poll();
}
List<String> res = new ArrayList<>();
while (!heap.isEmpty()) res.add(heap.poll());
Collections.reverse(res);
return res;
}
}!Common mistake
Getting the tie-break backwards inside the min-heap — it must be the reverse of the final order.
Complexity
- Time: O(n log k).
- Space: O(n).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon