Kth Largest Element in an Array
Find the kth largest element using sorting vs a min-heap of size k.
Kth Largest Element in an Array
Problem: Given an array of numbers and an integer k, find the kth largest element. Not the kth distinct — just the kth largest when sorted.
Example:
- Input:
nums = [3, 2, 1, 5, 6, 4],k = 2 - Output:
5(sorted descending:[6, 5, 4, 3, 2, 1], the 2nd is5)
Note
Think about it this way: you want the top k largest numbers. The kth largest is just the smallest of those top k.
How to Think About It
Starting point: The obvious move is to sort the array descending and return nums[k-1]. That works, but sorting all n elements is more work than the problem actually requires.
The realization: You don't need to rank all n elements. You just need to know which k elements are the largest. Once you have that set, the answer is the smallest one in it.
Why a min-heap of size k? You want to maintain a "running top-k" window. The weakest element in that window — the one you'd replace first if a better candidate arrives — is the minimum. A min-heap puts the minimum at the root, so you can check it in O(1) and evict it in O(log k).
The algorithm clicks: For each element, push it onto the heap. If the heap grows past k, pop the root (smallest). After processing everything, the root holds the k-th largest.
Why not a max-heap? A max-heap would give you the largest element instantly, but tells you nothing about the k-th largest without popping k times — O(k log n) total, which is worse.
Brute Force
View Brute Force
Optimal — Min Heap of Size k
View Optimal Solution
| Approach | Time | Space | When to use |
|---|---|---|---|
| Sort | O(n log n) | O(1) | Small arrays, simple situations |
| Min Heap | O(n log k) | O(k) | Large arrays, especially when k is small |