215. Kth Largest Element in an Array

Problem Statement

Pattern: Pattern Order Of Statistics

---

Code

public static int findKthLargestLib (int[] nums, int k) {
	PriorityQueue<Integer> pq = new PriorityQueue<>();
	int index = 0;
	while(k-- > 0) {
		pq.add(nums[index++]);
	}
	for(;index < nums.length;index++) {
		if(nums[index] >= pq.peek()) {
			pq.remove();
			pq.add(nums[index]);
		}
	}
	return pq.peek();
}
 

Notes

• Make a minHeap of size k of the largest elements of an array.
• The root will be the answer!

Quick Select Solution

Quick Sort

public static int findKthLargestLib (int[] nums, int k) {
	PriorityQueue<Integer> pq = new PriorityQueue<>();
	int index = 0;
	while(k-- > 0) {
		pq.add(nums[index++]);
	}
	for(;index < nums.length;index++) {
		if(nums[index] >= pq.peek()) {
			pq.remove();
			pq.add(nums[index]);
		}
	}
	return pq.peek();
}
 

Notes

• Make a minHeap of size k of the largest elements of an array.
• The root will be the answer!

Kth largest element in an infinite Array / Stream

https://www.google.com/amp/s/www.geeksforgeeks.org/kth-largest-element-in-a-stream/amp/

heap