Kth Largest
Maintain a min-heap of size K. For each new element: if heap has < K items, add it. Otherwise, if the element is larger than the heap's top (current Kth largest), replace the top. The heap's top is always the Kth largest.
How It Works
Finding the Kth largest element uses a min-heap capped at size K. Stream through the elements: while the heap holds fewer than K items, push freely; afterwards, compare each new element with the heap's top — the smallest of the current top K. If the newcomer is larger, pop the top and push the newcomer. At the end the heap contains exactly the K largest elements, and its top is the Kth largest.
The counterintuitive choice of a min-heap is the whole trick: to keep the K largest, you need fast access to the weakest member so it can be evicted. Total time is O(n log K) with O(K) space, which beats fully sorting at O(n log n) whenever K is small, and works on streams where the data cannot be stored or sorted at all.
Step-by-Step Visualization
Code
class KthLargest {
PriorityQueue<Integer> heap;
int k;
KthLargest(int k, int[] nums) {
this.k = k;
heap = new PriorityQueue<>();
for (int n : nums) add(n);
}
int add(int val) {
heap.add(val);
if (heap.size() > k) heap.poll();
return heap.peek();
}
}Tips & Gotchas
Practice Problems
- 1Kth Largest Element in an Array
- 2Kth Largest Element in a Stream
- 3Third Maximum Number
- 4Find K Pairs with Smallest Sums
About the Top K Elements Pattern
Use a min-heap of size K. As you process elements, if the current element is larger than the heap's minimum, swap it in. When done, the heap contains exactly the K largest elements. The top is the Kth largest.
Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.
Common Heap Interview Problems
- Kth Largest Element
- Top K Frequent Elements
- Find Median from Data Stream
- Merge K Sorted Lists
- Task Scheduler
- K Closest Points to Origin
Frequently Asked Questions
Why a min-heap for the K largest and not a max-heap?
A max-heap of all n elements gives quick access to the single largest, but finding the Kth requires K pops and O(n) memory. A size-K min-heap instead exposes the weakest of the current best K, which is exactly the element that should be evicted when something better arrives — using only O(K) space.
How does the heap approach compare with Quickselect?
Quickselect runs in O(n) average time but O(n²) worst case, needs all data in memory, and mutates the array. The heap runs in O(n log K), never degrades, and handles streaming input. Prefer Quickselect for one-shot in-memory queries and the heap for streams or repeated queries.