Heap · LC #215
Kth Largest Element in an Array
Maintain a min-heap of size k while scanning the array; the heap's minimum is the kth largest. Alternatively use QuickSelect for O(n) average time.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Find the `k`th largest element in an unsorted array (not the `k`th distinct element).
Sample I/O
Input: nums=[3,2,1,5,6,4], k=2 Output: 5 Input: nums=[3,2,3,1,2,4,5,5,6], k=4 Output: 4
Intuition
How to Think About It
Intuition
A min-heap of size k always holds the k largest elements seen so far. Its root is the smallest of those k elements - exactly the kth largest overall. When a new element exceeds the root, it displaces it.
Core Concept
Push each number into a min-heap. When size > k, pop the minimum. After full scan, heap root = kth largest. Time O(n log k), Space O(k). QuickSelect alternative: O(n) average, O(n²) worst.
When to use
Finding top-k elements from a stream; when k << n and you want O(n log k) rather than O(n log n) full sort.
When NOT to use
When you need the kth distinct element (requires deduplication first); when k == n (just sort); when worst-case O(n) matters (use median-of-medians QuickSelect).
Key Insights
What to Know Cold
- Min-heap of size k: root is always the kth largest seen so far.
- Push every element; if size > k, pop - heap maintains the top-k invariant.
- QuickSelect: partition array around pivot; recurse only into the relevant half. O(n) average.
- kth largest = (n−k+1)th smallest - sometimes easier to frame as kth smallest.
- For streaming/online input, heap approach is the only option; QuickSelect requires random access.
1 example
Worked Examples
Find 2nd largest in leaderboard
Scores [3,2,1,5,6,4], find k=2 largest.
Min-heap of size 2; scan and pop when oversized.
Output: 5
Streaming analytics (top-k products, top-k queries) and leaderboards use this pattern constantly.