Kth Largest Element in an Array
Find the kth largest element in an unsorted array.
Pattern fit
A min heap of size k keeps exactly the current top-k frontier, and the heap top is the kth largest by definition.
Key observation
You do not need full sorting; you only need to remember the best k values seen so far.
Target complexity
O(n log k) / O(k)
How to break down the solution cleanly
A min heap of size k keeps exactly the current top-k frontier, and the heap top is the kth largest by definition.
You do not need full sorting; you only need to remember the best k values seen so far.
Define what the heap top represents in one sentence.
Push new candidates as soon as they become eligible.
Reference implementation
Python# Generic pattern template
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
Common pitfalls
Using a max heap and popping k times when the min-heap-of-k idea is cleaner for large inputs.
Letting the heap grow beyond size k.
Common follow-ups
How would quickselect compare?
Why is the heap top the kth largest, not the largest?
Continue with related problems
Build repeatable depth inside the Heap / Priority Queue cluster before moving on.