Top K Frequent Words
Find the k most frequent words using sorting vs a min-heap with custom ordering.
Top K Frequent Words
Problem: Given an array of words and an integer k, return the k most frequent words. If two words have the same frequency, return them in alphabetical order. The result must be sorted by frequency (highest first).
Example:
- Input:
words = ["i","love","leetcode","i","love","coding"],k = 2 - Output:
["i","love"]— "i" appears 2×, "love" appears 2×, both tied but "i" < "love" alphabetically
Note
The twist compared to Top K Frequent Elements: when frequencies are equal, alphabetically smaller words rank higher. Your comparator must handle both dimensions.
How to Think About It
Starting point: Same as Top K Frequent Elements — count frequencies, sort by frequency descending, return first k. The twist: ties must be broken alphabetically ascending.
The comparison has two dimensions: First rank by frequency (higher = better). If tied, rank alphabetically (earlier = better). This tiebreaker must be baked into your comparator.
Why a min-heap gets tricky here: A min-heap evicts the "worst" candidate at the root. Worst means lowest frequency — but on a tie, it means alphabetically later (since you want to keep the alphabetically earlier word). So your heap comparator must define "smaller" as: lower frequency, or same frequency but alphabetically later. This feels backwards from the output order, but that's correct for a min-heap eviction strategy.
Mental check: If two words have the same frequency, the one that should be evicted first is the alphabetically later one, because you're keeping the earlier one. So "love" < "i" in the heap's ordering (love gets evicted first when tied), which is the opposite of natural string comparison.
Brute Force
View Brute Force
Optimal — Min-Heap of Size k
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Count + Sort | O(n log n) | O(n) |
| Count + Min-Heap | O(n log k) | O(n) |