Practice: Top K Frequent Words
Counter and a heap.
Given a long list of words, return the K most common ones. If two words are equally common, put them in alphabetical order. This shows up in search engines, and analytics everywhere.

- A long list of words
- The k most common
- Ties: alphabetical
Count, then pick
Counter counts every word in one pass. Then heap Q dot N smallest picks the top K, using a key of minus the count, then the word itself. Minus the count puts the most common first, and the word breaks ties alphabetically. Run it.
import heapq
from collections import Counter
words = "the cat and the dog and the bird saw a cat".split()
counts = Counter(words)
top = heapq.nsmallest(3, counts, key=lambda w: (-counts[w], w))
print(counts.most_common(4))
print(top)[('the', 3), ('cat', 2), ('and', 2), ('dog', 1)]
['the', 'and', 'cat']Costs
Counting is O of N. Picking the top K with a heap is O of M log K, where M is the number of different words. Sorting all of them would be O of M log M. And the tie breaking key is a handy trick. Tuples compare one item at a time, so you can sort by several things at once.
| key | value |
|---|---|
| Count | O(n) |
| Top k | O(m log k) |
| Ties | key=(−count, word) |
| Trick | tuples sort item by item |
Summary
Count with Counter, then pick the top K with a heap, using a tuple key for ties. Next, checking a Sudoku board.
Key takeaways- Counter
- heapq.nsmallest with a key
- Tuples break ties