Top K Frequent Words

Intuition

First count how many times each word appears. The answer needs a two-level ordering: frequency descending, then lexicographic ascending to break ties. Sorting the unique words with that composite comparator and taking the first k is the most direct route. Alternatively a heap of size k with the inverse comparator keeps memory at O(k); the tie-break direction must be flipped for the eviction heap so the least desirable word sits on top. Either way the key insight is encoding both rules into a single comparison.

Algorithm walkthrough

1. 1Tally each word's frequency in a hash map.
2. 2Define the ordering: higher frequency first, and for equal frequencies the lexicographically smaller word first.
3. 3Either sort all unique words by that ordering, or maintain a size-k heap using the reversed ordering and evict the weakest candidate.
4. 4If using a heap, pop the remaining elements and reverse them to restore descending order.
5. 5Return the first k words.

Implementation

import heapq
from collections import Counter


class Word:
    def __init__(self, word: str, freq: int):
        self.word = word
        self.freq = freq

    def __lt__(self, other: "Word") -> bool:
        if self.freq != other.freq:
            return self.freq > other.freq
        return self.word < other.word


class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        counts = Counter(words)
        heap = [Word(word, freq) for word, freq in counts.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap).word for _ in range(k)]