Kth Largest Value in an Array
Problem
Given an unsorted array and an integer k, return the kth largest element. Maintain a min-heap of size k: push every new value, and pop the smallest whenever the heap exceeds k. The root at the end is the answer.
Input
nums = [9, 4, 1, 7, 6, 5], k = 3Output
6The three largest values are {9, 7, 6}; the smallest of those is 6.
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]function kthLargest(nums, k) {
const heap = new MinHeap();
for (const x of nums) {
heap.push(x);
if (heap.size() > k) heap.pop();
}
return heap.peek();
}class Solution {
public int kthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
}int kthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int x : nums) {
heap.push(x);
if ((int)heap.size() > k) heap.pop();
}
return heap.top();
}