Q15: How do you find the Kth Largest Element in an Array using a Min-Heap and QuickSelect?
- Min-Heap Approach: Maintain a
PriorityQueueof size $k$. Iterate elements; push onto heap. If size $> k$, pop the minimum. Final heap top contains the $k$-th largest element. Time: $O(n log k)$. - QuickSelect Approach: Based on Partition step from QuickSort. Average time: $O(n)$.
Min-Heap Kth Largest Element Solution
import java.util.PriorityQueue;
public class KthLargest {
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}💡 Restricting heap capacity to $k$ elements leaves the $k$-th largest item at the top.
Key Takeaways
- Min-Heap of size $k$ maintains the $k$ largest elements seen so far.
- QuickSelect provides average $O(n)$ time complexity using partitioning.
Knowledge Check
What is the space complexity of finding the Kth largest element using a size-bounded Min-Heap?