< Back




692. Top K Frequent Words

We're asked to find the k most frequent words in a list of words. Super easy to solve with a min
heap. First, we grab the frequency of each word from the input list. We iterate through the words
and their frequency and maintain a min heap of size k. Maintenance in this case means that, when
the heap's size is greater than k, we pop the top element from the heap. This way, the top element
is always the minimum of the greatest k elements.

Finally, we sort our heap in descending order and return the result.

The solution is as follows:


  from collections import Counter
  from heapq import heappush, heappop

  class Pair:
      def __init__(self, word, freq):
          self.word = word
          self.freq = freq

      def __lt__(self, p):
          return self.freq < p.freq or (self.freq == p.freq and self.word > p.word)

  class Solution:
      def topKFrequent(self, words: List[str], k: int) -> List[str]:
          cnt = Counter(words)
          h = []
          for word, freq in cnt.items():
              heappush(h, Pair(word, freq))
              if len(h) > k:
                  heappop(h)
          return [p.word for p in sorted(h, reverse=True)]


_ Time Complexity:

  O(nlog(k)) - The usual time complexity for a heap when maintaining a heap of size k.

_ Space Complexity:

  O(n) - We store n elements in the heap in the worst case.