DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Top K Frequent Words

mediumHeaps and top-K Must-do

Problem statement

You get a list of words and an integer k. Return the k words that appear most often, ordered from most frequent to least frequent. When two words appear the same number of times, the one that comes first alphabetically goes first.

k is at most the number of distinct words.

Examples

Example 1

Input: words = ["deploy", "build", "deploy", "test", "build", "deploy"], k = 2

Output: ["deploy", "build"]

Explanation: deploy appears 3 times and build twice.

Example 2

Input: words = ["web", "db", "cache", "db", "web", "api"], k = 3

Output: ["db", "web", "api"]

Explanation: db and web both appear twice, so db comes first alphabetically. api and cache tie on one each, and api wins the last spot.

Hints

Approach

Count, then keep only the best k in a min-heap.

  1. Count occurrences with a hash map.
  2. Define "weaker": a lower count is weaker; with equal counts, the word later in the alphabet is weaker. The heap's root is always the weakest word it holds.
  3. Push each distinct word. If the heap holds more than k, pop the root.
  4. Pop everything left. It comes out weakest first, so reverse it to get the required order.

The tie-break direction is the subtle part: inside the heap the alphabet is reversed, because the word you want to throw away on a tie is the one later in the alphabet. In Python a small class with __lt__ expresses this cleanly, since negating a string is not possible.

ComplexityTime O(n + m log k)Space O(m)
Python
import heapq
from collections import Counter
class Entry:
"""Heap item where the 'smallest' entry is the weakest candidate."""
def __init__(self, count: int, word: str):
self.count = count
self.word = word
def __lt__(self, other: "Entry") -> bool:
if self.count != other.count:
return self.count < other.count # fewer occurrences = weaker
return self.word > other.word # same count: later in the alphabet = weaker
class Solution:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
counts = Counter(words)
heap = [] # min-heap of the k strongest words
for word, count in counts.items():
heapq.heappush(heap, Entry(count, word))
if len(heap) > k:
heapq.heappop(heap) # evict the weakest
result = []
while heap:
result.append(heapq.heappop(heap).word)
return result[::-1] # popped weakest-first, so reverse

Follow-up questions

  • The log is too large for memory. How would you find the top k words across many files or machines?
  • Return each word with its count, formatted as a report.

Frequently asked questions

That problem lets you return the answer in any order and has no ties to break. Here the output order matters and ties must be broken alphabetically, which is what makes the heap comparator tricky.

The root of a min-heap is the item that gets evicted. On a count tie you want to keep db and evict web, so web must count as smaller, which means comparing words in reverse. The final reverse then restores the normal order.

Reporting the top error messages, the busiest endpoints, or the most frequent user agents from a log is exactly this, and a stable, alphabetical tie-break keeps reports from changing order between runs when counts are equal.