Kth Largest Element in an Array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
