Given an array of strings words and an integer k, return the k most frequent words. Order the result from highest frequency to lowest, and break ties by putting the alphabetically smaller word first.
- 1 <= words.length <= 500
- 1 <= words[i].length <= 10
- words[i] has only lowercase letters
- 1 <= k <= number of distinct words
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
After counting with a hash map, the simplest approach sorts all distinct words by (-count, word), which is O(m log m) for m distinct words. Since we only need the first k, we can build a heap with the same key and pop just k times. In Python, heapify builds it in O(m), so the total is O(m + k log m). The key detail is the tie-break: equal counts must come out in alphabetical order.
Algorithm
- Count every word in a hash map.
- Build a heap of all distinct words, ordered by count descending and then word ascending.
- Pop
ktimes and append each word to the result. - Return the result.
O(n + k log m), with m distinct wordsSpace: O(m)class Solution: def topKFrequent(self, words: List[str], k: int) -> List[str]: count = Counter(words) # (-count, word): higher count first, then alphabetically smaller word heap = [(-c, w) for w, c in count.items()] heapq.heapify(heap) return [heapq.heappop(heap)[1] for _ in range(k)]