K Most Frequent Words
Problem
Given a list of words and an integer k, return the k words that occur most often, from most to least frequent. Words with the same count are ordered alphabetically, so the answer is always unique. k is at most the number of distinct words.
Examples
Input: words = ["red", "blue", "red", "green", "blue", "red"], k = 2
Output: ["red", "blue"]
Why: red appears 3 times, blue 2 and green 1Input: words = ["b", "a", "c", "a", "b", "c"], k = 2
Output: ["a", "b"]
Why: all three words appear twice, so the alphabetical tie-break picks a and bInput: words = ["solo"], k = 1
Output: ["solo"]
Why: edge case, a single word is its own top 1Hints
0 / 3
Count first with a hash map. After that the task is choosing k of the distinct words, and sorting all of them does more work than needed when k is small.
Define one ranking key that captures both rules: a higher count ranks first, and among equal counts the alphabetically smaller word ranks first. The tuple (-count, word) sorts exactly that way.
Keep only the k best words in a heap as you scan the counts. heapq.nsmallest(k, counts, key=...) does exactly that, returns them best first, and costs O(m log k) for m distinct words.
Solution
Counting is one pass with Counter. The two ordering rules fold into the single key (-count, word): negating the count makes more frequent words smaller, and the word itself breaks ties alphabetically, so "the k best words" becomes "the k smallest keys". heapq.nsmallest keeps a heap of only k candidates while it scans, evicting the worst one whenever a better word arrives, and returns the survivors sorted best first. The tie-break is where hand-rolled versions usually go wrong: a plain min-heap of (count, word) pairs evicts the alphabetically smaller word on a tie, which is the one you wanted to keep. Time is O(n + m log k) for n words and m distinct words, and space is O(m) for the counts.
import heapq
from collections import Counter
def top_k_words(words, k):
counts = Counter(words)
# best first: higher count, then alphabetical; only k candidates are kept in the heap
return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))
print(top_k_words(["red", "blue", "red", "green", "blue", "red"], 2)) # -> ['red', 'blue']
print(top_k_words(["b", "a", "c", "a", "b", "c"], 2)) # -> ['a', 'b']
print(top_k_words(["solo"], 1)) # -> ['solo']Stuck on the idea rather than the code? Top K in a Stream covers it.