Top K Frequent Words
Understanding the Problem
We have a list of words, some of which repeat, and we need to find the k most frequently occurring ones. So far this sounds identical to "Top K Frequent Elements," but there's a twist: when two words share the same frequency, they must be ordered alphabetically. The output must also be sorted by frequency (highest first), not returned in any order.
This tie-breaking requirement changes the problem. With numbers, you could return results in any order. Here, the custom sort has two keys: frequency (descending) and then lexicographic order (ascending). Every approach has to handle this dual ordering correctly, which is what drives the data structure choices below.
Key Constraints:
1 <= words.length <= 500: With n at most 500, even an O(n^2) solution would pass. The follow-up still asks for O(n log k), so the goal is to reach that bound.1 <= words[i].length <= 10: Words are short, so a single string comparison costs at most 10 character comparisons. We treat each comparison as O(1) and leave the word length out of the complexity analysis.words[i]consists of lowercase English letters, so there are no unicode or special-character cases to handle.kis in[1, number of unique words], so k never exceeds the number of distinct words and the answer always has exactly k entries.
Approach 1: Sort by Custom Comparator
Intuition
Count every word's frequency, then sort the unique words using a comparator that handles both criteria: frequency descending first, and alphabetical order ascending to break ties. Take the first k words from the sorted list.
The comparator is the whole solution. Once the list is sorted by these two keys, the answer is the prefix of length k, and the output ordering is already correct because we sorted by the same keys the output requires.
Algorithm
- Build a hash map
freqmapping each word to its count. - Collect all unique words into a list.
- Sort the list with a custom comparator: compare by frequency descending first, then by word lexicographically ascending for ties.
- Return the first
kwords from the sorted list.
Example Walkthrough
Code
- Time Complexity: O(n log n). Counting frequencies takes O(n). Sorting the unique words takes O(m log m) where m is the number of unique words. In the worst case m = n, so this is O(n log n).
- Space Complexity: O(n). The frequency map stores up to n entries. The candidate list holds at most n unique words.
Sorting orders all m unique words even though only k are needed. The next approach keeps a running set of only k candidates and discards the rest as it scans, which lowers the log factor from log m to log k.
Approach 2: Min-Heap
Intuition
A min-heap of size k holds the current top k candidates while we scan. Push each unique word into the heap, and when the heap grows past k, pop one word. After processing every word, the heap holds the top k.
The heap's comparator is the reverse of the output ordering. The result wants high frequency and, for ties, low alphabetical order. So the heap's minimum (the element that gets popped) must be the word that is worst by those criteria: lowest frequency, and for ties, highest alphabetical order.
The pop only ever removes the heap's minimum, which is the worst of the current k+1 candidates by frequency then alphabetical order. A word is discarded only when k strictly better words already sit in the heap, so no word that belongs in the final top k is ever removed. The heap yields elements from worst to best, so reversing the extraction order produces frequency-descending, alphabetical-ascending output.
Algorithm
- Build a frequency map from
words. - Create a min-heap with a custom comparator: compare by frequency ascending first (lower frequency = smaller = gets popped first), and for equal frequencies, compare by word descending alphabetically (alphabetically later = less desirable = gets popped first).
- For each unique word, add it to the heap. If heap size exceeds k, pop the minimum.
- Extract elements from the heap. Since the heap gives them in min-first order, reverse the result.
Example Walkthrough
Code
- Time Complexity: O(n log k). Building the frequency map is O(n). For each of the m unique words, we do a heap push and potentially a pop, each O(log k). Total is O(n + m log k). Since m <= n, this is O(n log k).
- Space Complexity: O(n). The frequency map uses O(n) space. The heap holds at most k elements. Total is O(n).
The heap approach meets the O(n log k) follow-up. The next approach removes the log factor on the frequency dimension by grouping words directly into buckets indexed by frequency, leaving only the per-bucket alphabetical sort.
Approach 3: Bucket Sort
Intuition
The maximum frequency any word can have is n, the case where every element is the same word. Create an array of n+1 buckets where bucket[i] holds all words with frequency i. Frequency is an integer in [1, n], so it serves directly as an array index without any comparisons. Walking from the highest bucket down to the lowest visits words in decreasing-frequency order.
Words sharing a bucket all have the same frequency, so they must come out in alphabetical order to satisfy the tie-breaking rule. Sorting each bucket on its own handles that. The combined size of all buckets is m unique words, so the total sorting cost stays bounded by O(m log m).
Algorithm
- Build a frequency map from
words. - Create a bucket array of size n+1. For each unique word, add it to
bucket[frequency]. - Sort each non-empty bucket alphabetically.
- Walk from the highest index down to 0. For each bucket, collect words into the result until we have k words total.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n + m log m) where m is the number of unique words. Building the frequency map is O(n). Creating and filling buckets is O(m). Sorting all buckets combined takes O(m log m) in the worst case. Walking the buckets to collect k words is O(n).
- Space Complexity: O(n). The frequency map uses O(m) space. The bucket array has n+1 slots. The result list holds k words. Total is O(n).