Pattern 1: Top-K with a heap of size K
"The K largest", "the K-th smallest", "the K most frequent" — a whole family of problems. The key insight: you do not need to sort everything. All you need is a heap that keeps only the K best seen so far.
Try it first: Kth Largest Element in an Array
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Return the k-th LARGEST element of nums (the k-th in decreasing order, counting repetitions).
Example: nums = [3,2,1,5,6,4], k = 2 → 5.
(In Python there is heapq; in JS, the solution includes a small heap class, since the language has no native one.)
Tried it? Sorting the array and taking the right position works (O(n log n)) — and it passes! But there is an approach that is better when K is small and the stream is large. The theory below shows the heap of size K.
The theory: a fixed-size heap of K
To find the K-th largest, keep a min-heap with at most K elements — the K largest seen so far. The trick is counterintuitive: to keep the largest ones, use a min-heap, because that way the smallest of the K large ones sits at the top, easy to discard:
for each number x:
push x onto the heap
if the heap exceeded K elements:
remove the top (the smallest) → the K largest remain
at the end: the top of the heap is the K-th largest
Why does it work? The heap always holds the K largest so far; its smallest element (the top) is exactly the K-th largest. Any number smaller than that top is discarded right away.
Why O(n log k) — and when is it worth it?
There are n elements; each push/pop costs O(log k) (the heap never
exceeds K). Total: O(n log k), with O(k) space. Compare it to sorting
everything (O(n log n), O(n) space): when k is much smaller than n, log k ≪
log n, and the heap wins — plus it works for streams (data that arrives bit
by bit), where sorting everything would not even be possible.
| Approach | Time | Space | Good when |
|---|---|---|---|
| Sort everything | O(n log n) | O(n) | you need everything sorted |
| Heap of size K | O(n log k) | O(k) | K ≪ n, or a stream |
Example: Top K Frequent Elements
"The K elements that appear most." It combines two patterns you already have:
frequency counting (hash map, from the Array/String section) + top-K with
a heap. Count the frequencies, then use a heap of size K over the pairs
(frequency, element):
The lesson: for the K largest, use a MIN-heap
The inversion is the confusing part — and that is why it is worth fixing in your mind: K largest → min-heap of size K (the top is the "gatekeeper", the smallest of the large ones, ready to be evicted). K smallest → max-heap of size K (the top is the largest of the small ones). Keeping only K, and discarding the wrong extreme, is what gives the O(n log k).
🧠 Review quiz
0/41. To find the K LARGEST elements, why use a MIN-heap (and not a max-heap)?
2. Why is the heap of size K O(n log k) and not O(n log n)?
3. When is the heap of size K preferable to simply sorting the array?
4. How does Top K Frequent combine patterns you already know?
Summary
- Top-K: keep a heap of size K with the K best; the top is the K-th.
- K largest → min-heap; K smallest → max-heap (the top is what gets discarded).
- O(n log k), O(k) space — beats sorting when K ≪ n or in streams.
- Top K Frequent = hash map (count) + heap of size K.
Next lesson: the heap picking the next smallest among K sources — k-way merge.