AI Hints
Home›DSA in Python Tutorial›More Practice: Backtracking and Graphs
DSA in Python · Lesson 123 of 132

Practice: Top K Frequent Words

Counter and a heap.

⏱ 2 min read▶ Video at 2:26:37🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Top K Frequent Words
From the video: Practice: Top K Frequent Words
  • 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.

top_words.pypython
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)
Output
[('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.

keyvalue
CountO(n)
Top kO(m log k)
Tieskey=(−count, word)
Tricktuples 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
Next up: Practice: Valid Sudoku — sets for rows, columns, boxes