Top-K Elements Pattern
The Top-K elements pattern finds the K smallest, largest or most frequent elements in a dataset without fully sorting it.
SHELF OF 3
ADMIT
WEAKEST
The stream
10 arrives and the shelf is not full yet, so it goes straight in. Shelf: 10.
Next
5 arrives and the shelf is not full yet, so it goes straight in. Shelf: 5, 10.
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".
Applying for software engineering roles? Free, no sign-up: