Back to Heap / Priority Queue
Medium
Kth Largest Element in an Array
Given an integer array `nums` and an integer `k`, return the `k`th largest element in the array. Note that it is the `k`th largest element in the sorted order, not the `k`th distinct element. Can you solve it without sorting?
Examples
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 <= 10^5-10^4 <= nums[i] <= 10^4
Approach
Maintain a Min Heap of size `k`. Iterate through the array and push each element onto the heap. If the heap size exceeds `k`, pop the smallest element. After processing all elements, the heap will contain the `k` largest elements from the array, and the root (the smallest among them) will be the `k`th largest element overall.
Complexity Analysis
Time Complexity
O(N log K)
Space Complexity
O(K)
This approach is highly consistent and space-efficient compared to a full sort (O(N log N)).
Solution.java
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); } } return minHeap.peek(); }}