Skip to main content
CodeEasy v0.1

Top K Frequent Words

Medium Subject: Heap / Priority Queue
Time Complexity
O(N log K)
Space Complexity
O(N)

Problem Description

Problem Statement

Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

  • Input: words = ["i","love","leetcode","i","love","coding"], k = 2
  • Output: ["i","love"]

Optimal Solution

Python

Approach: Min-Heap

Count frequencies. We use a min-heap of size k. To handle lexicographical order naturally in a min-heap, we push tuples of (-frequency, word). When the heap size exceeds k, we pop the smallest. Finally, we reverse the result.

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        count = Counter(words)
        heap = []

        for word, freq in count.items():
            heapq.heappush(heap, (-freq, word))

        res = []
        for _ in range(k):
            res.append(heapq.heappop(heap)[1])

        return res