Given an integer array nums and an integer k,
return the kth largest element in the array.
Note: it is the kth largest in sorted order, not the kth distinct element.
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
- 1 <= k <= nums.length <= 105
- -104 <= nums[i] <= 104
Contents
- Approach 1 — Sort O(n log n)
- Approach 2 — Min-Heap of size k O(n log k)
- Complexity Analysis
Sort
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k]; // kth from the end
}
Simple but O(n log n). We can do better.
Min-Heap of size k
Maintain a min-heap of size exactly k. When the heap exceeds k,
remove the minimum. At the end, the root of the heap is the k-th largest.
Why? After processing all elements, the heap holds the k largest values.
The minimum of those k values (the heap root) is the k-th largest overall.
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min at top
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // remove the smallest, keep top-k
}
}
return minHeap.peek(); // kth largest
}
| Approach | Time | Space |
|---|
| Sort | O(n log n) | O(1) |
| Min-Heap size k | O(n log k) | O(k) |
Min-heap approach is preferred when k is much smaller than n (streaming data, memory constraints).