Top K Frequent Words
Return the k most frequent words, breaking ties lexicographically.
Open on LeetCode ↗Intuition
Ordering purely by frequency looks sufficient, but it isn't: ties must break LEXICOGRAPHICALLY, and the two orderings actually run in OPPOSITE directions. The final answer wants frequency descending but the word ascending. In a fixed-size min-heap that means the comparator has to invert the frequency comparison to keep evicting the worst entry, while leaving the word comparison alone to keep tie-breaking correctly, and mixing that up is exactly where people go wrong. Count first, then compare pairs of (word, count) with frequency as the primary key and the word as the secondary key, always in that asymmetric direction.
A bounded min-heap of size k with a two-part ordering: higher count wins, and among equal counts the lexicographically smaller word wins. Since the heap evicts the worst, the tie-break must be inverted inside it — hence the negated character codes.
Approach
Count occurrences
Build a frequency map from word to count in one pass, remembering first-seen order only for readability, since the map itself is what the ranking reads from.
Maintain a bounded min-heap of size k
Push each distinct word with its count into a heap ordered so the WORST candidate sits at the top: lowest frequency, and on a tied frequency, the lexicographically LARGER word (since it should rank worse). Whenever the heap exceeds k, evict that top entry.
Read out in the opposite order
Once every word has been considered, sort the surviving heap entries by frequency descending, breaking ties by word ascending -- the mirror image of the eviction comparator -- to produce the final list.
Solution & live demo
Common pitfalls
Ignoring the lexicographic tie-break
heapq.heappush(heap, (c, w))
entry = (c, [-ord(ch) for ch in w], w)
With equal counts the answer must prefer the alphabetically earlier word. A plain tuple compares words ascending, so the min-heap evicts the smaller one — exactly backwards.
Sorting the whole frequency map
return sorted(counts, key=lambda w: (-counts[w], w))[:k]
if len(heap) > k: heapq.heappop(heap)
Correct, and often fast enough — but it's O(n log n) in the number of distinct words when only the top k are needed. The bounded heap is O(n log k) and O(k) space.
Returning the heap without a final sort
return [e[2] for e in heap]
heap.sort(key=lambda e: (-e[0], e[2]))
A heap only guarantees its root; the rest is in arbitrary internal order. The k survivors are the right set but need sorting into the required output order.
Edge cases
every distinct word is returned, ordered by the same frequency-desc, word-asc rule
the frequency tie-break becomes the only rule, so the k lexicographically smallest words win
it always ranks first regardless of k, since nothing can outrank its frequency
standard lexicographic string comparison decides the tie, matching Python's native string ordering