Kth Largest Element in an Array Given an integer array nums
and an integer k
, return the kth
largest element in the array.
Note that it is the kth
largest element in the sorted order, not the kth
distinct element.
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Constraints:
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
Kth Largest Element in an Array Solutions
✅Time: O(n log k)
✅Space: O(k)
C++
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<>> minHeap;
for (const int num : nums) {
minHeap.push(num);
if (minHeap.size() > k)
minHeap.pop();
}
return minHeap.top();
}
};
Java
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
for (final int num : nums) {
minHeap.offer(num);
while (minHeap.size() > k)
minHeap.poll();
}
return minHeap.peek();
}
}
Python
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
minHeap = []
for num in nums:
heapq.heappush(minHeap, num)
if len(minHeap) > k:
heapq.heappop(minHeap)
return minHeap[0]
Watch Tutorial
Checkout more Solutions here