Top K Elements¶
Also known as: Heap, Priority Queue, K Largest / K Smallest
Keep a heap of exactly K items as you stream through the data, evicting the worst each time it overflows. You never sort the whole input — you only ever maintain the K that matter.
Before you start¶
- Comfortable with basic array operations and comparison logic in your language.
What 'solved properly' looks like
Target: O(n log k). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
As you walk through the data, you maintain a heap (usually a min-heap) of exactly K elements. For each new element, you add it, and if the heap exceeds K, you remove the smallest — which is the one you're least interested in. When you finish, the heap holds the K largest items. The counter-intuitive part: to keep the K largest, you use a min-heap, so the weakest survivor sits on top ready to be evicted.
Why it matters: It's the first pattern that handles data too big to sort — and the min-heap-for-max inversion is a genuine mental upgrade. Paired with a frequency counter, it solves "top K most frequent" problems in one pass without ever sorting the full data.
When to reach for it¶
Reach for it when you see "top K", "Kth largest/smallest", "K closest", "most frequent", or streaming data where you only need a few results from a huge input.
When not to use it
The heap type is inverted from intuition — for K largest you keep a min-heap so the weakest survivor sits on top, ready to be evicted. If K is close to n, just sort (O(n log n)) — the heap only wins when K is small. And if you need only the single Kth element and nothing else, Quickselect averages O(n) and beats this.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Last Stone Weight | LeetCode | Easy | 15 mins | teaching |
| 2 | Kth Largest Element in a Stream | LeetCode | Easy | 15 mins | teaching |
| 3 | Top K Frequent Elements | LeetCode | Medium | 25 mins | consolidation |
| 4 | K Closest Points to Origin | LeetCode | Medium | 25 mins | consolidation |
| 5 | Kth Largest Element in an Array | LeetCode | Medium | 25 mins | challenge |
Already know this? Test out.
If you can solve Kth Largest Element in an Array cleanly in one sitting — using a heap (or Quickselect if you're feeling confident) — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.