← All patterns
Heaps / Priority Queues (Top-K)
Maintain a min/max-heap of a bounded size to efficiently track the K largest/smallest elements without sorting everything.
When to use it
- 'Kth largest/smallest', 'top K frequent', merging K sorted lists, median-of-stream problems.
Signals in the problem statement
- Keyword 'K' combined with largest/smallest/frequent/closest.
Common pitfalls
- Using a max-heap of all N elements instead of a min-heap capped at size K (wastes O(n log n) vs O(n log k)).
- Forgetting most languages' heap libraries are min-heaps by default — negate values for a max-heap in Python, for example.
Practice Problems
Top K Frequent Elements
MediumAsked at: Amazon, Meta, Google
Given an integer array, return the k most frequent elements.
Time: O(n log k) · Space: O(n)
Kth Largest Element in a Stream
EasyAsked at: Amazon, Google
Design a class that keeps track of the kth largest element in a stream of numbers as elements are added one at a time.
Time: O(log k) per add · Space: O(k)
Merge K Sorted Lists
HardAsked at: Amazon, Meta, Google, Microsoft
Given k sorted linked lists, merge them into one sorted list.
Time: O(N log k), N = total nodes · Space: O(k)
Kth Largest Element in an Array
MediumAsked at: Amazon, Meta, Microsoft, Apple
Find the kth largest element in an unsorted array.
Time: O(n log k) · Space: O(k)