Top-K Elements Pattern
A technique to find the K smallest, largest, or most frequent elements in a dataset without fully sorting it.
Top 3 "Hall of Fame"
Ready to process stream.
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Suppose you want to find the top 10 richest people out of 8 billion. Sorting everyone is overkill!
Instead, we only care about maintaining a small list of the "best so far". The Top-K Elements pattern typically uses a Heap to track these elite items efficiently.
Concept
The Strategy:
- K Largest: Use a **Min-Heap** of size K. If a new number is larger than the root (minimum of the top K), swap it.
- K Smallest: Use a **Max-Heap** of size K. If a new number is smaller than the root (maximum of the bottom K), swap it.
- QuickSelect: An alternative based on QuickSort partitioning (average O(N)).
How it Works
The visualizer shows items arriving one by one.
- A shelf holds K items.
- When a new item arrives, we compare it to the "weakest" item on the shelf.
- If the new item is better, the weak one is kicked out.
Step-by-Step Breakdown
1. Initialize Min-Heap of size 0.
2. For each `num` in array: `heap.push(num)`.
3. If `heap.size() > K`: `heap.pop()` (remove smallest).
4. Result is the heap contents.
When to Use
- "Find the K largest/smallest/most frequent..."
- Streaming data (finding trends in real-time).
- When K is much smaller than N (O(N log K) vs O(N log N)).
When NOT to Use
- When K is close to N (Sorting might be faster due to constant factors).
- When you need the exact rank of every element.
How to Identify
"Top K", "Kth largest", "Most frequent K items".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.