Top K Frequent Words
Top K Frequent Elements: return the k most frequent words, breaking ties lexicographically.
- 1 <= words.length <= 500
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters.
- k is in the range [1, The number of unique words[i]]
Intuition
Top k frequent words returns the k most frequent words, and the tie-breaking rule is what makes it more than a counting exercise:
- Words with equal frequency must be ordered lexicographically, so the comparison is by frequency descending and then by word ascending — two keys running in opposite directions.
That opposition is the detail most solutions get wrong. Sorting by a single key, or by both in the same direction, produces output that looks right on inputs without ties and fails as soon as two words share a count.
Counting is a single pass into a hash map. The ordering is then the real work, and three approaches serve different values of k.
Sorting all distinct words by the two-key comparator is simplest, at O(n log n) where n is the distinct word count. Perfectly good when k is close to n.
A min-heap of size k is better when k is small. Push words and evict the smallest whenever the heap exceeds k, then read the result. This gives O(n log k) — but the heap's comparator must be inverted relative to the final ordering, since the element to evict is the least desirable, which is the higher-lexicographic word among tied counts.
That inversion is subtle enough to be worth writing out carefully rather than reasoning about in the moment.
The heap yields results in reverse order, so the output must be reversed before returning.
Bucket sort by frequency is O(n) but requires sorting each bucket alphabetically, which reintroduces a log factor per bucket.
A bounded min-heap of size k with a two-part ordering: higher count wins, and among equal counts the lexicographically smaller word wins. Since the heap evicts the worst, the tie-break must be inverted inside it — hence the negated character codes.
Approach
Before reading on: price up what counting everything costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(n log k) time and O(n) space.
Count word frequencies
One pass into a hash map gives each distinct word's count. The ordering that follows is where the actual difficulty lies.
Order by two opposing keys
Frequency descending, then word ascending. The two keys run in opposite directions, which is what most incorrect solutions miss.
Sort when k is large
Sorting all distinct words with that comparator is O(n log n) and simplest. Preferable when k approaches the distinct count.
Use a size-k min-heap when k is small
Push and evict beyond k for O(n log k). The heap holds the current best k without ever sorting the rest.
Invert the heap comparator
The element to evict is the least desirable — lower frequency, or higher lexicographic among ties. The heap's order is the reverse of the output's.
Reverse the heap's output
A min-heap yields the weakest first, so the collected result must be reversed before returning.
Cost of the approaches
Counting is O(n). Sorting gives O(n log n); the heap gives O(n log k). Both use O(n) space for the counts.
Solution & live demo
Common pitfalls
Ignoring the lexicographic tie-break
heapq.heappush(heap, (c, w))
entry = (c, [-ord(ch) for ch in w], w)
With equal counts the answer must prefer the alphabetically earlier word. A plain tuple compares words ascending, so the min-heap evicts the smaller one — exactly backwards.
Sorting the whole frequency map
return sorted(counts, key=lambda w: (-counts[w], w))[:k]
if len(heap) > k: heapq.heappop(heap)
Correct, and often fast enough — but it's O(n log n) in the number of distinct words when only the top k are needed. The bounded heap is O(n log k) and O(k) space.
Returning the heap without a final sort
return [e[2] for e in heap]
heap.sort(key=lambda e: (-e[0], e[2]))
A heap only guarantees its root; the rest is in arbitrary internal order. The k survivors are the right set but need sorting into the required output order.
Edge cases
every distinct word is returned, ordered by the same frequency-desc, word-asc rule
the frequency tie-break becomes the only rule, so the k lexicographically smallest words win
it always ranks first regardless of k, since nothing can outrank its frequency
standard lexicographic string comparison decides the tie, matching Python's native string ordering