Top K Frequent Words
Problem statement
You're given a list of strings, words, and a number k. Return the k words that appear most often.
Order the result by how often each word appears, from most frequent to least. If two words appear exactly the same number of times, put the one that comes first alphabetically ahead of the other.
Examples
Example 1
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" both appear twice, more than any other word, and "i" comes before "love" alphabetically, so it's listed first.
Example 2
Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the" appears 4 times, "is" appears 3 times, "sunny" appears 2 times, and "day" appears once — all four counts are different, so the alphabetical tiebreak never comes into play here.
Hints
Approach
Optimal: Min-heap capped at size k
Intuition
Sorting every unique word does more work than necessary once you realize the goal is only to find the top k — everything below the top k never actually needs to be placed in order relative to each other. A min-heap capped at size k keeps just the current best k candidates, evicting the single worst one whenever a better candidate needs room.
Deciding what "worst" means here needs both parts of the ranking rule: the worst candidate is the one with the lowest count, and among candidates tied on count, the alphabetically largest one is considered worse (since the problem prefers alphabetically smaller words when counts tie). Keeping that specific word at the top of the heap is what lets the eviction step throw away exactly the right candidate each time.
Steps
- Count how many times each word appears, using a hash map.
- Build a min-heap ordered so that its top is always the current "worst" candidate — the lowest count, or, if tied, the alphabetically largest word.
- For each unique word, push it onto the heap. If the heap now holds more than
kwords, pop the top — this evicts exactly the worst candidate seen so far. - Once every word has been processed, the heap holds the best
kcandidates, but in worst-to-best order (since the worst was always at the top and easiest to check). - Pop everything off the heap and reverse the resulting list to get it in best-to-worst order, matching what the problem asks for.
Dry run
words = ["i","love","leetcode","i","love","coding"], k = 2 (counts: i=2, love=2, leetcode=1, coding=1)
| word pushed | heap holds (conceptually, worst on top) | over capacity? | evicted |
|---|---|---|---|
| i | {i:2} | no | — |
| love | {i:2, love:2} | no | — |
| leetcode | {i:2, love:2, leetcode:1} | yes (size 3 > 2) | leetcode:1 (lowest count) |
| coding | {i:2, love:2, coding:1} | yes | coding:1 (lowest count) |
After processing every word, the heap holds {i:2, love:2}. Popping both off (worst-first, which for this tied pair means "love" comes off before "i", since "love" is alphabetically larger) and then reversing gives ["i", "love"], matching the expected output.
Edge cases: when k equals the number of unique words, nothing is ever evicted, so the heap simply ends up holding every unique word, in some order, and the final reverse still produces the fully correct ranking. Ties on count are resolved correctly because the heap's ordering rule explicitly checks alphabetical order as a second key, not just as an afterthought during the final sort.
Complexity
Time O(n log k) - counting is O(n), and each of the u unique words triggers at most one push and one pop on a heap that never exceeds size k, so each operation costs O(log k). This matches the O(n log k) bound the problem's own follow-up asks for.
Space O(n) - the frequency map holds up to n entries in the worst case (every word distinct), while the heap itself never holds more than k.
import heapq
from collections import Counter
class Word:
"""Wraps a word so the heap can compare words in reverse lexicographic
order, without changing how counts are compared."""
__slots__ = ("word",)
def __init__(self, word: str):
self.word = word
def __lt__(self, other: "Word") -> bool:
return self.word > other.word # reversed: alphabetically larger sorts "smaller"
class Solution:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
freq = Counter(words)
heap = [] # min-heap of (count, Word), capped at size k
for word, count in freq.items():
heapq.heappush(heap, (count, Word(word)))
if len(heap) > k:
heapq.heappop(heap) # evicts the lowest count, or the alphabetically largest among ties
result = []
while heap:
_, wrapped = heapq.heappop(heap)
result.append(wrapped.word)
result.reverse() # heap pops worst-first, so reverse to get best-first
return result
if __name__ == "__main__":
print(Solution().topKFrequent(["i", "love", "leetcode", "i", "love", "coding"], 2))
# ['i', 'love']
print(Solution().topKFrequent(["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], 4))
# ['the', 'is', 'sunny', 'day']RecapThe whole problem in a few lines, for the night before
- Spot it: "top k most frequent" with a secondary tiebreak (here, alphabetical order) that has to be respected exactly
- Idea: count with a hash map, then keep a min-heap capped at size k whose ordering encodes both the count and the reversed tiebreak, so eviction always removes the true worst candidate
- Cost: O(n log k) time, O(n) space (sorting every unique word up front is O(u log u), where u is the number of unique words)
- Trap: forgetting to reverse the alphabetical comparison inside the heap's ordering — the heap needs the alphabetically *larger* tied word to look "smaller" so it gets evicted first, which is the opposite of normal string comparison
Interview follow-ups
The follow-up asks for O(n log k) time and O(n) extra space — does the heap approach actually meet that bound?
Yes: counting frequencies is O(n) time and O(u) space for u unique words (at most n), and each of the u heap operations costs O(log k) since the heap never holds more than k words, giving O(u log k) total, which is within the O(n log k) the follow-up asks for. The O(n) extra space comes from the frequency map and the heap, both bounded by the number of unique words.
What if instead of the k most frequent words, you needed the k least frequent words (with the same alphabetical tiebreak for the least frequent)?
Flip which end of the ranking the heap protects: cap a max-heap at size k instead, where the heap's top is now the highest-count word (or, among ties, the alphabetically smallest), so that the least-frequent candidates are the ones kept and the most-frequent ones get evicted first.
Frequently asked questions
The heap's ordering decides what counts as "worst" so that popping the top always evicts the right candidate. Since the problem prefers alphabetically smaller words when counts tie, the alphabetically larger word among a tied pair is the one that should be evicted first — so it needs to appear as the heap's "smallest" (highest eviction priority) element, even though that reverses the normal alphabetical comparison.
The heap always keeps the current worst candidate at the top, which is exactly why popping is useful during the eviction step — but that also means values come off the heap from worst to best, the opposite of the order the problem wants. Reversing that popped order at the very end restores the best-to-worst order the answer needs.
Bucket sort by frequency works cleanly for plain numbers because ties can be broken arbitrarily, so words can just be dropped into buckets by count with no further ordering needed. Here, words tied on count must still come out in alphabetical order, and enforcing that ordering needs a comparison-based sort somewhere — either up front (as in the brute force approach) or built into the heap's comparator (as in the heap approach) — so the log factor doesn't fully disappear the way it does for numeric-only Top K problems.
Ranking the most frequent error messages, endpoint paths, or log tokens — with a consistent, deterministic tie-break so the same output always comes back for the same input — mirrors exactly this kind of "top k by frequency, alphabetical tiebreak" ranking, which shows up in log analysis and monitoring dashboards.
