Find the kth largest element in an unsorted array without fully sorting it.
Maintain a min-heap of size k. Stream every element through: push it onto the heap, then if the heap exceeds size k, pop the minimum. After processing all elements, the heap's minimum is the kth largest — it is the smallest among the top-k values seen so far.
How to think about it
Recognise the pattern
The signal is “kth largest / kth smallest / top-k elements” without needing a full sort. A min-heap of fixed size k is the canonical tool: it always evicts the smallest element seen so far, so after processing the whole array it holds exactly the k largest values, and its root is the kth largest. For streaming data or large arrays where sorting is expensive, this is O(n log k) — much better than O(n log n).
Build the approach step by step
Brute force: sort descending, return index k-1. O(n log n) time, O(1) extra space. Simple but overkill.
Quickselect: O(n) average, O(n²) worst case — great in practice but tricky to implement correctly under interview pressure.
Min-heap of size k: easy to code, guarantees O(n log k):
- Push each element onto the heap.
- If
len(heap) > k, pop the minimum (this element is not in the top-k). - After the loop,
heap[0]is the answer.
Walk through nums=[3,2,1,5,6,4], k=2:
push 3 -> [3]
push 2 -> [2,3] size==k, stop popping
push 1 -> [1,2,3] -> pop 1 -> [2,3]
push 5 -> [2,3,5] -> pop 2 -> [3,5]
push 6 -> [3,5,6] -> pop 3 -> [5,6]
push 4 -> [4,5,6] -> pop 4 -> [5,6]
heap[0] = 5 -> 2nd largest ✓Complexity
- Time — O(n log k): each of the n elements does at most one push and one pop on a heap of size k. Each heap operation is O(log k).
- Space — O(k): the heap holds at most k+1 elements at any moment.