Kth Largest Element
Finding the kth largest (or smallest) element in an array is a classic problem that can be solved efficiently with a heap. Use a min-heap of size k to find the kth largest (or max-heap for kth smallest).
Kth Largest Element using Min-Heap of size k
1. Insert first k elements into a min-heap.
2. For remaining elements, if element > heap root, pop root and insert element.
3. At the end, root of heap is the kth largest.
Java implementation:
public static int findKthLargest(int[] nums, int k) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
Time Complexity: O(n log k).
For kth smallest, use max-heap of size k.
Two Minute Drill
- Kth largest element: maintain min-heap of size k.
- Kth smallest: maintain max-heap of size k.
- Time O(n log k), space O(k).
- Heap approach works for streaming data.
Need more clarification?
Drop us an email at career@quipoinfotech.com