Kth Largest Element in an Array
Medium · heap
Given a list of integers nums and an integer k, return the kth largest value in the list.
"kth largest" is about sorted order, not about distinct values: if the list were sorted from biggest to smallest, you want the number at position k (counting from 1). Duplicates each take their own position.
Try to do better than sorting the whole list.
Examples
Example 1
Input: nums = [7, 3, 9, 1, 5], k = 2
Output: 7
Sorted from largest, the list is [9, 7, 5, 3, 1], and the 2nd value is 7.
Example 2
Input: nums = [4, 4, 1, 2, 4], k = 3
Output: 4
Duplicates count separately: [4, 4, 4, 2, 1], so the 3rd value is still 4.
Example 3
Input: nums = [-2, -9, -4], k = 1
Output: -2
Constraints
- 1 <= k <= len(nums) <= 10^4
- -10^4 <= nums[i] <= 10^4