You are given a list of integers nums and an integer k. Return the k-th largest value: the
value that would sit at position k (counting from 1) if nums were sorted from largest to
smallest.
Equal values count separately, so in [5, 5, 1] the largest and the second largest are both 5.
Try to do better than sorting the whole list.
Example 1
- Input
- nums = [4, 9, 1, 7, 3], k = 2
- Output
- 7
Example 2
- Input
- nums = [6, 2, 6, 5, 1], k = 2
- Output
- 6
Constraints
- 1 ≤
k≤ length ofnums≤ 10⁵ - Every value is between −10⁴ and 10⁴.
Show the pattern
Heap
Only the k largest values seen so far can matter, and the answer is the smallest of them. A min-heap capped at k items keeps exactly those values, with that smallest one on top.
See heap in a visualiserShow the approach
Walk through the list keeping a min-heap of the k largest values seen so far. Push each number; if the heap now holds k + 1 values, pop the smallest, which can't be among the k largest. After the walk the heap holds the k largest values, and its top, the smallest of them, is the k-th largest.
Quickselect (partition around a pivot as quicksort does, then continue into one side only) takes O(n) on average, but it rearranges the list, and an unlucky run takes O(n²).
Time: O(n log k) · Space: O(k)