Given an integer array nums and an integer k, return the kth largest element in the array (the kth largest in sorted order, not the kth distinct element).
Example 1
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted descending: 6,5,4,3,2,1 — the 2nd largest is 5.
1 <= k <= nums.length <= 10^5Sorting the whole array works but does more work than necessary — you only need to know ONE position's value.
A min-heap of size k, not a max-heap of the whole array, is the efficient approach — think about why the heap should hold the k LARGEST seen so far, with the smallest of those at the top.
Once the heap has k elements, any new element smaller than the heap's top can be discarded immediately without ever entering the heap.
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min-heap: smallest of the top-k sits at the top
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll(); // discard the smallest — it can't be in the top k anymore
}
return minHeap.peek(); // the smallest element remaining IS the kth largest overall
}Time: O(n log k) · Space: O(k)