Kth Largest Element in an Array
Medium ArrayDivide and ConquerSortingHeap (Priority Queue)Quickselect
Given an array of integers and a position
k, find the element that would rank kth if sorted in descending order. The key insight is recognizing that you don't need to sort the entire array—you only need to maintain the top k candidates efficiently.Description
You are given an array of integers nums and a positive integer k. Return the kth largest element in the array.
Note: You are looking for the kth largest in sorted order, not the kth distinct value. For example, if the array is [3, 3, 2, 1] and k = 2, the answer is 3 (the second largest), not 2 (the second distinct value).
Challenge: Can you solve this more efficiently than sorting the entire array?
Examples
Input: nums = [6,5,4,8,9,7], k = 2
Output: 8
Explanation: When sorted in descending order:
[9,8,7,6,5,4]. The 2nd largest is 8.Input: nums = [7,4,6,3,4,8,9,9,10], k = 4
Output: 7
Explanation: Sorted descending:
[10,9,9,8,7,6,4,4,3]. The 4th largest is 7.Input: nums = [2,1], k = 2
Output: 1
Explanation: The 2nd largest element is
1.Constraints
1 ≤ k ≤ nums.length ≤ 10⁵- Each element
nums[i]is in the range[-10⁴, 10⁴]
Hints
Code Editor