Top K Frequent Words
Problem
Given an array of strings words and an integer k, return the k most frequent strings in words. The answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
- 1 ≤ words.length ≤ 50000
- 1 ≤ words[i].length ≤ 10
- words[i] consists of lowercase English letters.
- k is in the range [1, Number of unique words]
Example
words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2["i", "love"]The word "i" appears twice, "love" appears twice, and the others appear once. Since "i" and "love" have the same frequency, they are sorted alphabetically, so "i" comes before "love".
Approach
Straightforward Solution
A brute-force approach would count frequencies and then sort all words by frequency descending and lexicographical ascending. This approach is straightforward but sorting all unique words can be costly if the number of unique words is large.
Core Observation
The problem requires identifying the most frequent words and sorting them by frequency and lexicographical order. Frequency counting is a fundamental step, and sorting by multiple criteria is necessary to meet the ordering requirements.
Path to Optimal
The key recognition signals are 'k most frequent', 'sorted by frequency', and 'lexicographical order for ties'. These indicate a priority queue or sorting approach. Counting frequencies with a hash map is standard. Sorting the unique words by a custom key that orders by negative frequency and then lex order achieves the desired order efficiently. Since the problem constraints allow sorting all unique words, this approach is optimal and simpler than maintaining a heap.
Optimal Approach
Count the frequency of each word using a hash map (Counter). Extract the unique words and sort them with a custom key: first by negative frequency (to get descending order), then by lexicographical order (ascending). Return the first k words from this sorted list. This approach is efficient and straightforward, leveraging Python's stable sort and tuple comparison.
Time
O(n + m log m)
Counting frequencies takes O(n) time where n is the number of words. Sorting the m unique words takes O(m log m) time. Since m ≤ n, the overall complexity is O(n log n) in the worst case.
Space
O(m)
The hash map stores frequencies for m unique words, requiring O(m) auxiliary space. The sorted list also requires O(m) space. This space is necessary to store frequency information and the unique words.
Pattern Spotlight
Heap / Priority Queue (Frequency Sorting with Custom Comparator)
When asked for the top k frequent elements with tie-breaking rules, first count frequencies with a hash map, then sort or use a heap with a custom comparator that orders by frequency descending and lexicographical ascending to efficiently retrieve the top k.
Solution
| 1 | class Solution: |
| 2 | def topKFrequent(self, words: List[str], k: int) -> List[str]: |
| 3 | count = Counter(words) |
| 4 | |
| 5 | words = list(count.keys()) |
| 6 | |
| 7 | words.sort(key=lambda w: (-count[w], w)) |
| 8 | |
| 9 | return words[:k] |
Step-by-Step Solution
Count Frequencies of Each Word Using a Hash Map
| 3 | count = Counter(words) |
Objective
To build a frequency map that records how many times each word appears in the input list.
Key Insight
Counting frequencies is the foundation for identifying the most frequent words. Using a hash map (Counter) provides O(1) average-time insertion and lookup, enabling a single pass over the input words to build the frequency distribution efficiently.
Interview Quick-Check
Core Logic
Use a hash map to count occurrences of each word in O(n) time.
Complexity
Counting frequencies requires O(n) time and O(m) space, where m is the number of unique words.
Extract Unique Words and Sort by Frequency and Lexicographical Order
| 5 | words = list(count.keys()) |
| 7 | words.sort(key=lambda w: (-count[w], w)) |
Objective
To order the unique words by descending frequency and ascending lexicographical order to satisfy the problem's output requirements.
Key Insight
Sorting with a custom key that uses negative frequency ensures that words with higher counts come first. Using the word itself as the second key ensures that ties are broken alphabetically. Python's sort is stable and efficient, making this approach both simple and performant.
Interview Quick-Check
Core Logic
Sort unique words by (-frequency, word) to get descending frequency and ascending alphabetical order.
Common Pitfalls & Bugs
Forgetting to negate frequency leads to ascending frequency order, which is incorrect.
Complexity
Sorting takes O(m log m) time, where m is the number of unique words.
Return the Top K Words from the Sorted List
| 9 | return words[:k] |
Objective
To select and return the first k words from the sorted list as the final answer.
Key Insight
After sorting, the top k words are the first k elements of the list. This direct slicing operation is O(k) and straightforward, completing the solution efficiently.
Interview Quick-Check
Core Logic
Return the first k elements from the sorted list to get the top k frequent words.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
words.sort(key=lambda w: (-count[w], w))Sort the unique words by descending frequency and ascending lexicographical order.
The custom sort key (-count[w], w) ensures that words with higher frequency come first, and ties are broken alphabetically, exactly matching the problem's ordering requirements.
count = Counter(words)Count the frequency of each word in the input list using Counter.
Using Counter efficiently builds a frequency map in O(n) time, which is essential for identifying the most frequent words without repeated scanning.
words = list(count.keys())Extract the list of unique words from the frequency map keys.
Isolating unique words allows sorting only the distinct elements, reducing the problem size from n to m (number of unique words), which is critical for efficiency.
return words[:k]Return the first k words from the sorted list as the result.
Slicing the sorted list to length k efficiently extracts the top k frequent words, completing the solution.
Test Your Understanding
Why is sorting by (-frequency, word) the correct way to order the words for this problem?
Sorting by negative frequency ensures words with higher frequency come first, and sorting by the word lexicographically ensures that ties in frequency are broken by alphabetical order, exactly matching the problem's ordering requirements.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Top K Frequent Words from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Top K Frequent Words drill