Kth Largest Element in an Array
Return the k-th largest element (not distinct) without fully sorting.
Open on LeetCode ↗Intuition
Keep a min-heap of the k largest seen so far — its root is always the current k-th largest. Anything smaller than the root can't matter; anything bigger evicts the root. n pushes into a size-k heap beats a full sort when k ≪ n.
"Top k" almost always means a heap of size k — and the counter-intuitive part is that you want a min-heap for the k largest. The root is then the weakest survivor, so one comparison decides whether a newcomer belongs. Sorting is O(n log n) and computes far more order than the question asked for; the heap is O(n log k) and holds only what matters.
Approach
Why a MIN-heap for largest
The gatekeeper of 'top k' is the smallest member of that club — exactly what a min-heap exposes at its root.
Stream the array through
Seed the heap with the first k values, then for each remaining value compare it against the root. If it is not larger, it cannot belong to the top k — skip it entirely. If it is larger, heapreplace swaps it in and sifts down in one step, evicting the old minimum. Invariant: the heap always holds the k largest elements seen so far.
Alternative: quickselect
Partition around a pivot and recurse into the side containing index n−k — O(n) average, O(n²) worst; the heap is the safe default.
Solution & live demo
Common pitfalls
Using a max-heap for the k largest
heap = [-n for n in nums]
heapq.heapify(heap)
for _ in range(k - 1):
heapq.heappop(heap)
return -heap[0]heap = nums[:k]
heapq.heapify(heap)
for n in nums[k:]:
if n > heap[0]:
heapq.heapreplace(heap, n)
return heap[0]It works, but it holds all n elements — O(n) space and no better than sorting when k is small. A min-heap capped at k keeps only the current top k, and its root is exactly the k-th largest by construction.
Pushing then popping instead of replacing
heapq.heappush(heap, n) heapq.heappop(heap)
heapq.heapreplace(heap, n)
Same result, two heap operations instead of one — and the heap transiently grows to k+1. heapreplace pops and pushes in a single sift-down.
Comparing with >= and doing pointless work
if n >= heap[0]:
heapq.heapreplace(heap, n)if n > heap[0]:
heapq.heapreplace(heap, n)Swapping a value for an equal one leaves the multiset identical while paying a full sift-down. Harmless for correctness, wasteful on inputs with many duplicates.
Edge cases
Heap holds everything; root is the minimum — correct.
'k-th largest' counts repeats; the heap does so naturally.