Top K Frequent Words Solution

Problem

Given a list of words and an integer k, return the k words that appear most often in the list, ordered from most frequent to least frequent. When two words appear the same number of times, the one that comes earlier alphabetically should appear first in the result.

Input: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: Both "i" and "love" appear twice — the most of any word — and "i" precedes "love" alphabetically.

Second example showing the tie-breaking rule at work:

Input: words = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: Frequencies are the=4, is=3, sunny=2, day=1, so all four unique words are returned in that order.

Intuition

The problem is really two tasks glued together: count how often each word appears, then pick and order the top k. The ordering rule — descending frequency, alphabetical for ties — can be encoded as a single comparison key: negate the frequency so that higher frequencies sort first, then let natural string comparison handle the tie. For inputs where k is much smaller than the number of unique words, a min-heap of size k avoids sorting every word and brings the time cost down from O(n log n) to O(n log k).

Approach 1 — Count and Sort

Count every word's frequency with a hash map, then sort the unique words using a two-part key: descending frequency first, ascending alphabetical order for ties. Return the first k results.

Count each word's occurrences.
Sort unique words by (-frequency, word).
Return the first k words from the sorted list.

1from collections import Counter
2
3def topKFrequent(words: list[str], k: int) -> list[str]:
4    frequency = Counter(words)
5    # (-frequency, word) sorts descending by count, then ascending alphabetically
6    return sorted(frequency.keys(), key=lambda word: (-frequency[word], word))[:k]

Time: O(n log n) — counting is O(n), sorting m unique words takes O(m log m) ≤ O(n log n).

Space: O(n) — the frequency map and sorted list each hold at most n entries.

Approach 2 — Min-Heap of Size k

Maintain a min-heap of at most k candidates. For each new word, push it onto the heap; if the heap grows beyond k, pop the "worst" word (lowest frequency, or alphabetically latest for ties). The heap always holds exactly the current top-k winners. After processing all words, collect and reverse the heap to get the final order.

Count each word's frequency.
For each unique word, push it onto a min-heap ordered by "worst first" (lowest frequency, then alphabetically latest for ties).
If the heap exceeds k entries, pop the worst candidate.
Drain the heap into the result list and reverse it.

1import heapq
2from collections import Counter
3
4def topKFrequent(words: list[str], k: int) -> list[str]:
5    frequency = Counter(words)
6
7    class Entry:
8        def __init__(self, word):
9            self.word = word
10        def __lt__(self, other):
11            # "Less than" here means "worse" — this element should be evicted first
12            if frequency[self.word] != frequency[other.word]:
13                return frequency[self.word] < frequency[other.word]  # lower freq is worse
14            return self.word > other.word  # alphabetically later is worse for same freq
15
16    heap = []
17    for word in frequency:
18        heapq.heappush(heap, Entry(word))
19        if len(heap) > k:
20            heapq.heappop(heap)  # evict the worst candidate when heap exceeds k
21
22    result = []
23    while heap:
24        result.append(heapq.heappop(heap).word)
25    return result[::-1]  # heap yields worst-first; reverse for best-first

Time: O(n log k) — counting is O(n); each of the m unique words is pushed and possibly popped from a heap of size k, costing O(m log k) ≤ O(n log k).

Space: O(n) — the frequency map is O(n); the heap holds at most k+1 entries, O(k).

Complexity Summary

Approach	Time	Space	When to use
Count and Sort	O(n log n)	O(n)	Simple to write; best when k is close to n or code clarity matters more than throughput
Min-Heap of Size k	O(n log k)	O(n)	Best when k is much smaller than the number of unique words and throughput matters

Common Mistakes

Forgetting that the tie-breaking rule is alphabetical ascending, not descending — with (-frequency, word) as the sort key, ties break alphabetically ascending naturally, but with a heap it is easy to accidentally invert the comparator and sort later words first.
Using if instead of while in a loop when counting — Counter handles this automatically, but a manual loop using if freq[word] > 0 instead of freq[word] += 1 will undercount repeated words.
Inverting the heap comparator in C++ by confusing priority_queue semantics — C++'s priority_queue is a max-heap by default, so the comparator's "less than" relation determines what sinks to the bottom; swapping the intended ordering causes the best words to be evicted instead of the worst.
Collecting heap results in the wrong order — the min-heap pops the worst elements first, so the result must be reversed after draining the heap; skipping the reverse produces a bottom-k result.
Using subList in Java without copying — List.subList(0, k) returns a view of the backing list, which can cause unexpected behavior if the original list is modified; wrap it in new ArrayList<>() when returning from a method.

Top K Frequent Words — Solution