MediumArrayHash TableStringTrieSortingHeap (Priority Queue)Bucket SortCounting

Top K Frequent Words

1 approach, code in every language

You are given a list of words and an integer k. Return the k words that appear most frequently.

Order the answer by frequency from highest to lowest. When two words occur the same number of times, place the lexicographically smaller word first.

Example 1

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

Output: ["i","love"]

"i" and "love" both appear twice; the others appear once, so the two most frequent words are returned.

Example 2

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4

Output: ["the","is","sunny","day"]

Counts are the:4, is:3, sunny:2, day:1, so they are ordered by decreasing frequency.

Constraints

1 <= words.length <= 500
1 <= words[i].length <= 10
words[i] consists of lowercase English letters
k is in the range [1, the number of unique words]
Words with the same frequency are ordered lexicographically

Frequency Count + Composite Ordering

Count word frequencies, then order unique words by descending frequency and ascending lexicographic order, taking the first k (via sort or a size-k heap).

Loading animation…

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

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

Time

O(n log n) when sorting all unique words, or O(n log k) with a size-k heap

Space

O(n)

n is the number of words. The heap variant (Java/C++/C#/Python) keeps only k candidates by reversing the comparator so the least desirable word is evicted first.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Most Drawn Part Codes is our own problem on the technique behind Top K Frequent Words: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free