Kth Largest Element in an Array
Medium· min-heap· top k· quickselect
Problem
Return the kth largest element of an unsorted integer array, where duplicates count as separate positions in sorted order. Try to beat a full sort.
Examples
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
Sorted descending: 6,5,5,4,... so the fourth is 4.
Constraints
- • 1 <= k <= nums.length <= 10^5
- • -10^4 <= nums[i] <= 10^4
Hints & approach
Hint 1
Sorting works in O(n log n); can you avoid ordering everything?
Hint 2
A size-k min-heap keeps the k largest values.
Hint 3
Quickselect partitions like quicksort but only recurses into one side.
Approachtry the hints first
Stream the array through a min-heap capped at size k: push each value and pop when the size exceeds k. The root is then the kth largest, in O(n log k). Quickselect is the alternative: partition around a random pivot and recurse only into the side containing index n - k, giving O(n) expected time. The heap version is simpler to get right and works on streams.
Time O(n log k) heap, O(n) average quickselect · Space O(k)