Pattern 12: Top K Elements

Deep Dive: Min-Heap as a Bouncer

"Only the K Largest May Enter"

nums = [3, 1, 5, 12, 2, 11], k = 3:

Process 3:  heap=[3]          size < k, push
Process 1:  heap=[1,3]        size < k, push
Process 5:  heap=[1,3,5]      size == k
Process 12: 12 > heap[0]=1   pop 1, push 12. heap=[3,5,12]
Process 2:  2 < heap[0]=3    REJECTED (too small for top-3)
Process 11: 11 > heap[0]=3   pop 3, push 11. heap=[5,11,12]

Top-3 = [5, 11, 12]. Kth largest = heap[0] = 5.

The min-heap acts as a bouncer: it keeps the K largest elements and rejects anything too small to make the cut.

---

Signal: "K largest", "K smallest", "K most frequent" Template: Min-heap of size K (see Heaps in templates.py)

When to Use

• "Kth largest element"
• "Top K frequent elements"
• "K closest points to origin"

Key Insight

For K LARGEST: use a MIN-heap of size K. Root = Kth largest.
For K SMALLEST: use a MAX-heap of size K. Root = Kth smallest.
Always O(n log k) -- better than sorting O(n log n) when k << n.

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Kth Largest Element	Phase 1.8	15 min	[ ]
Top K Frequent Elements	Phase 1.8	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "K largest / K smallest / K most-frequent / K closest" — the literal word "K" combined with an extreme is the loudest signal.
• "Stream of numbers, report the K-best so far on demand" — a size-K heap is built for exactly this.
• "K closest points to the origin" or "K closest stars to Earth" — geometric variant; same heap pattern with a custom key.
• k ≪ n in the constraints — heap of size K runs in O(n log k), strictly better than full-sort when k is much smaller than n.

Anti-signals (looks like this pattern, isn't)

• "Sort the entire array" or "return the K largest in sorted order" when K is close to n — just sort; the heap doesn't help.
• "Median of a stream" — Two Heaps, not a single Top-K heap.
• "Kth smallest element in a sorted matrix" — heap works but Binary Search on the value is often the intended faster solution.
• "Find the K-th element in O(n) average" — Quickselect, not a heap.