Top K Frequent Words
Given a non-empty list of words, return the top K frequent words in the list. The output should be sorted by frequency from highest to lowest. If two words have the same frequency, they should be sorted alphabetically.
Constraints:
- 1 <= words.length <= 10^5
- 1 <= K <= words.length
- words[i] consists of only lowercase English letters.
Examples:
Input: ["i", "love", "leetcode", "i", "love", "coding"], 3
Output: ["i", "love", "coding"]
Explanation: The words "i", "love", and "coding" have the highest frequency, and they are sorted alphabetically.
Solutions
Hash Table and Heap
Time: O(N log K)Space: O(N)
We use a hash table to count the frequency of each word, and then use a heap to sort the words by frequency and alphabetically.
function topKFrequent(words, k) {
const frequency = {};
for (const word of words) {
frequency[word] = (frequency[word] || 0) + 1;
}
const heap = Object.keys(frequency);
heap.sort((a, b) => frequency[b] - frequency[a] || a.localeCompare(b));
return heap.slice(0, k);
}
Follow-up:
What if the input is a stream of words and we need to find the top K frequent words at any given time?
