Problem
Given an integer array nums and an integer k, return the kth largest element in the array. The kth largest element is based on its position in sorted order, not the kth distinct value.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [3,2,1,5,6,4]
k = 2 Output
5Solution
This solution uses a Min Heap of size k. The heap stores the k largest elements seen so far.For each number, it is added to the heap. If the heap size becomes greater than k, the smallest element is removed. This ensures that only the k largest elements remain in the heap.
After processing all elements, the smallest element in the heap is the kth largest element.
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
// Keep only the k largest elements.
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
Complexity
Each insertion or removal from the Min Heap takesO(log k) time. Since all n elements are processed, the overall time complexity is O(n log k).
The heap stores at most k elements, resulting in
O(k) extra space.