Community Problem
Top K Frequent Words
Difficulty: Medium
Return the k most frequent words, breaking frequency ties alphabetically and returning results in descending frequency.
Top K Frequent Words
Return the k most frequent words, breaking frequency ties alphabetically and returning results in descending frequency.
By CodeSnatch
April 18, 2026
·
Updated May 18, 2026
262 views
8
4.5 (15)
I see this problem rejected as "easy, just sort" by mid-level engineers, then watch them stumble on the tie-break in the 30-second window after a senior interviewer asks the follow-up. The full version of the problem (O(n log k) with a min-heap of size k) requires a comparator that breaks frequency ties alphabetically, which means the ordering inside the heap is non-trivial: less frequent loses, and on a frequency tie, the larger string loses. The catalog covers Top K Frequent Elements (numeric) but skipped this string variant where the tie-break is the whole interview signal.
Top K Frequent Words
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order (ascending).
Examples
Example 1:
- Input:
words = ["i", "love", "leetcode", "i", "love", "coding"],k = 2 - Output:
["i", "love"] - Explanation:
"i"and"love"are the two most frequent words. Both appear twice. The tie is broken by lexicographical order:"i" < "love".
Example 2:
- Input:
words = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is", "day"],k = 4 - Output:
["the", "is", "day", "sunny"] - Explanation: Frequencies are
the=4,is=3,sunny=2,day=2. The top two are unambiguous.dayandsunnytie at frequency 2, and the tie-break is lex ASCENDING, sodaycomes beforesunny.
Example 3:
- Input:
words = ["hello"],k = 1 - Output:
["hello"] - Explanation: Single word, single result.
Example 4:
- Input:
words = ["a", "aa", "aaa"],k = 1 - Output:
["a"] - Explanation: All three frequencies are 1. The one with the smallest lexicographical order wins.
Constraints
1 <= words.length <= 500.1 <= words[i].length <= 10.words[i]consists of lowercase English letters.kis in the range[1, number of unique words[i]].
Follow-up
The naive approach is to sort all unique words by (frequency desc, word asc) in O(u log u) where u is the unique-word count. Can you do it in O(u log k) with a min-heap of size k? You will need a comparator that pops the "least good" item: the one with the smallest frequency or, on a tie, the lexicographically LARGEST word.
Solution
Hints
Solution Walkthrough
Approach: Frequency Map + Composite-Key Sort (O(n + u log u))
The straightforward solution counts frequencies, then sorts the list of unique words by the composite key (-frequency, word). The minus sign on frequency flips that field's natural ascending order to descending, while the word itself stays ascending for the alphabetical tie-break. Slice the first k and return.
In Python, this is one sorted(..., key=lambda x: (-x[1], x[0])). In JavaScript, the comparator function does the same job: compare frequencies descending, then strings ascending.
The Heap Variant (O(n + u log k))
The interview follow-up replaces the sort with a min-heap of size k. The subtle part is the comparator. The heap must always be willing to pop the least good entry, where "least good" means low frequency OR (on a frequency tie) high lexicographical order.
- Python: push
(-frequency, word)onto a max-heap-by-negation. But that breaks the lex tie-break. The fix is to push(frequency, ReverseString(word))into a true min-heap, or to switch to a custom heap. The cleanest answer isheapq.nsmallest(k, items, key=lambda x: (-x[1], x[0])), which isO(u log k). - JavaScript: a
MinHeapkeyed by[frequency, word]with the comparator: pop when the new candidate has a frequency strictly greater than the smallest, OR equal frequency with a lexicographically smaller word.
For production code on the words.length <= 500 constraint, the sort version is plenty fast and far easier to read.
Algorithm (Sort Version)
- Build a frequency map by counting words.
- Extract the unique-word list.
- Sort by
(frequency descending, word ascending). - Return the first
k.
Why It Works
The sort is total under the composite key, so ties at frequency are resolved by the lex comparator and the result is fully deterministic. Slicing the prefix gives the top-k because the sort was descending on frequency.
Complexity
Sample frequency table
Word Count
the 4
is 3
sunny 2
day 2Top-4 sorted by (-count, word):
the (-4, the)
is (-3, is)
day (-2, day)
sunny (-2, sunny)Metric Value
Time O(n) to count + O(u log u) to sort = O(n + u log u)
Space O(u) for the map and the unique listPitfalls
- Negating both fields. Negating the word for lex tie-break (e.g. comparing reversed strings or trying to negate strings) is wrong. Only the frequency is negated; the word's own ascending order is what we want.
- Heap comparator. If you go the heap route, the comparator must invert frequency but NOT invert lex order. Many candidates get this backwards on first pass.
- Sorting all of
wordsinstead of unique keys. If duplicates remain in the sort target, the sort isO(n log n)instead ofO(u log u)and the output may include duplicates. Always dedupe via the frequency map first.
Solution Code