← All patterns
Top K Elements
Bounded heap of size k: min-heap for top-k-largest, max-heap for top-k-smallest. When one-shot O(n) average is acceptable, quickselect partitions around a pivot instead.
18 problems
4 Easy 8 Medium 6 Hard
Selection problems where you want the k largest (or smallest) out of n. Two approaches: bounded heap of size k (always O(n log k), simple, streaming-friendly), or quickselect (O(n) average, O(n²) adversarial worst case without random pivots, one-shot). Bucket sort wins when the value distribution is bounded — frequencies live in `[1, n]`, so bucketing gives O(n).
The mirror trick: min-heap of size k keeps the k *largest* (small candidates evicted); max-heap of size k keeps the k *smallest*.
When to reach for this pattern
- k largest / smallest values in an array or stream
- k most frequent elements (combine with hash-map frequency count)
- k closest points to origin / pivot
- Streaming top-k where new elements arrive over time
Canonical template
// bounded min-heap of size k → keeps the k largest
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : nums) {
pq.push(x);
if ((int)pq.size() > k) pq.pop();
}
// pq now holds the k largest; pq.top() is the kth-largest.
// bucket sort for frequencies (range bounded by n)
vector<vector<int>> buckets(n + 1);
for (auto& [v, f] : freq) buckets[f].push_back(v);C++ · adapt the names and types to your problem.
Common pitfalls
- Sorting the whole array is O(n log n) — bounded heap is strictly better when k ≪ n
- Quickselect needs random pivot or median-of-three to avoid the adversarial O(n²) case
- On streaming top-k with duplicates, hash-map + heap of (count, value) pairs avoids re-pushing
- Bucket sort only fits when the key range is small and known
Related patterns
Problems (18)
- Medium
- Easy
- Medium
- Medium
- Medium
- Medium
- Medium
- Easy
- Easy
- Hard
- Hard
- Hard
- Hard
- Hard
- Hard
- Medium
- Medium
- Easy