← DSA Atlas
Dedicated problem page · #692

Top K Frequent Words

MediumHeap and Priority QueueCount then heap-order by frequency and wordHash map counting + heap with composite key
Solve on LeetCode ↗
692
MediumHeap and Priority QueueHash map counting + heap with composite keyCount then heap-order by frequency and word

Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent words. Sort the result by descending frequency; words with the same frequency are ordered lexicographically (alphabetically ascending).

Open official problem prompt ↗
In plain English

Return the k words that appear most often, breaking frequency ties alphabetically, in the correct ranked order.

Picture it like this

A song chart ranks tracks by play count. Two tracks tied on plays are listed alphabetically. You count every play, then read off the top k from the chart.

Example
Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i", "love"]
Why
"i" and "love" each appear twice (more than any other word); tie broken alphabetically, and both beat the frequency-1 words.
Constraints
1 <= words.length <= 5001 <= words[i].length <= 10words[i] consists of lowercase English lettersk is in the range [1, number of unique words]
Pattern lesson

See the pattern, then code

Count then heap-order by frequency and word
Recognition clue

Top-k by frequency with a deterministic tie-break by string order signals counting into a hash map, then ordering by a composite key (frequency, word) with a heap.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. Count occurrences, then let a heap sort by a two-part key: highest frequency first, and for equal frequencies the alphabetically smaller word first. Negating the frequency turns Python's min-heap into 'largest frequency, then smallest word', so popping k times yields the answer directly.

New words, made simpleKnow these before the algorithm
Composite key
A sort key with multiple parts compared in order — here frequency first, then the word.
Lexicographic order
Dictionary order, comparing strings character by character.
Heapify
Rearranging a list into heap order in a single O(M) pass.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Count then full sort

Perfectly correct and simple; does slightly more work than needed when k is tiny relative to M.

Count words and sort all distinct words by (-frequency, word), slice the first k.

Time O(N + M log M)Space O(M)
Best choiceCount + heap of all, pop k

Avoids sorting the whole set fully; the composite key handles the tie-break cleanly.

Heapify (-freq, word) pairs and pop k times.

Time O(N + M + k log M)Space O(M)
The rule we keep true

Invariant

Every heap entry is keyed by (-frequency, word), so the heap root is always the highest-frequency word and, among ties, the lexicographically smallest one not yet popped.

Why this is correct

Reasoning

Tuple comparison compares -frequency first, so more frequent words (more negative key) come out first; when frequencies tie, comparison falls through to the word, and since we do NOT negate the string, ascending alphabetical order is preserved. Popping k times therefore emits exactly the required ranking.

The algorithm in three movesSay these aloud before coding
1Count each word's frequency with a hash map

counts: i=2, love=2, leetcode=1, coding=1

2Build heap entries (-frequency, word) for every distinct word

heap keys: (-2,'i'),(-2,'love'),(-1,'coding'),(-1,'leetcode')

3Heapify so the root is highest-frequency, then lexicographically smallest

pop 'i', pop 'love' -> ['i','love']

4Pop k times and collect the words

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
i:20
love:21
leetcode:12
coding:13
1 · Readwords
2 · AskHow often does each appear?
3 · Update statei=2, love=2, leetcode=1, coding=1
4 · ResultTwo words tie at frequency 2.
Key takeaway

Words ranked by frequency then alphabetically; top 2 highlighted.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 7Count words

    Counter builds a word to frequency map in one linear pass.

  2. 2
    Lines 8Composite keys

    Negate the frequency so higher counts sort first while the word stays un-negated for ascending ties.

  3. 3
    Lines 9Heapify

    One O(M) pass turns the list into a valid min-heap ordered by the composite key.

  4. 4
    Lines 10Pop k

    Each pop yields the next word in ranked order; take its string component.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k equals the number of distinct words (return all, fully ranked)
  • All words identical
  • Multiple words tied on frequency requiring alphabetical ordering
  • Single-word input
!

Common beginner mistakes

  • Negating the word as well as the frequency, which reverses the alphabetical tie-break
  • Sorting only by frequency and leaving ties in arbitrary (insertion) order
  • Using a max-heap over frequency alone, which does not resolve the lexicographic tie
  • Off-by-one on how many times to pop
Check your understanding

Why negate the frequency but NOT the word in the heap key?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#703Kth Largest Element in a StreamFixed-size min-heap (bounded top-k)