Top K Frequent Words
Medium · Heap & Counting · Array · Hash Table · String · Trie · Sorting · Heap (Priority Queue) · Bucket Sort · Counting
Problem
Given a list of words and an integer k, return the k most frequent words, ranked from the most frequent to the least.
Words with the same frequency are ranked alphabetically, in dictionary order, so "a" comes before "ab" and "ab" before "b". The order of the returned list is part of the answer.
Examples
Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"]
"i" and "love" both appear twice, more than any other word. They tie, so they are ranked alphabetically: "i" before "love".
Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 Output: ["the","is","sunny","day"]
"the" appears 4 times, "is" 3 times, "sunny" twice and "day" once.
Constraints
- 1 <= len(words) <= 10^4
- 1 <= len(words[i]) <= 10
- words[i] consists of lowercase English letters
- 1 <= k <= the number of distinct words
Approaches
- Pick the best remaining word, k times — time O(n + k · d), space O(d)
Follow-up
Could you do it in O(n log k) time and O(n) extra space?
Related problems
Start free on Cariara · Coding problems · System design studio
