Kth Largest Element
Find the kth largest element in an unsorted array of integers. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Constraints:
- 1 <= k <= nums.length
- 1 <= nums.length <= 10^4
- 10^3 <= nums[i] <= 10^3
Examples:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Explanation: The sorted array is [1,2,3,4,5,6], so the 2nd largest element is 5.
Solutions
Sorting
Time: O(n log n)Space: O(1)
This solution first sorts the array in descending order, then returns the kth element.
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}Priority Queue
Time: O(n log k)Space: O(k)
This solution uses a priority queue to keep track of the k largest elements seen so far.
function findKthLargest(nums, k) {
let queue = [];
for (let num of nums) {
if (queue.length < k) {
queue.push(num);
queue.sort((a, b) => b - a);
} else if (num > queue[queue.length - 1]) {
queue.pop();
queue.push(num);
queue.sort((a, b) => b - a);
}
}
return queue[queue.length - 1];
}
Follow-up:
How would you optimize the solution if the array is too large to fit into memory?
