Pattern this teaches:Heap and Top K
Top K Frequent Words
A medium Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 1
- Core for
- 10 roles
The problem
Count how often each word appears and return the k most common ones, most frequent first. When two words appear the same number of times, the one that comes earlier alphabetically goes first.
Example 1
- Input
- words = ["go","py","go","js","py","go"], k = 2
- Output
- ["go", "py"]
- Why
- "go" appears three times, "py" twice, "js" once.
Example 2
- Input
- words = ["red","blue","red","green","blue","red","green","teal"], k = 3
- Output
- ["red", "blue", "green"]
- Why
- "red" appears three times; "blue" and "green" both appear twice and "blue" wins the tie alphabetically.
Constraints
- 1 <= words.length <= 500
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters
- k is in the range [1, number of unique words]
How to think about it
Updated 2026-09-29The comparison between two words is compound: higher frequency wins, but on a tie, lexicographically smaller wins. If you use a bounded heap of size k to drop the losers, the worst candidate in the heap is the one with lower frequency, or on tied frequency, the one that is lexicographically larger.
Approaches, worst first
Sort all unique words
time O(u log u * L) · space O(u * L)
Count frequencies into a map. Extract unique words and sort with a custom comparator: frequency descending, then word ascending lexicographically. Slice the first k words.
Bounded min-heap of size kWrite this one
time O(u log k * L) · space O(u * L)
Maintain a size-k heap where the root is the least desirable word: lower frequency, or higher lexicographical order on ties. When full, evict the root. Finally, pop and reverse to deliver the result in descending order.
Where people lose marks · 3
- Reversing the tie-breaker inside the heap comparator. In a min-heap capped at k, the root must be the element you want to discard first, so tied frequencies must consider the lexicographically larger string as smaller in priority.
- Returning the heap extraction order directly without reversing. Popping a min-heap produces increasing priority, whereas the final answer demands strictly decreasing priority.
- Comparing strings with numerical subtraction instead of localeCompare or standard string operators.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .