215. Kth Largest Element in an Array

#array #quick_select

For an integer array nums and an integer k, return the kth largest element in the array.

---

To find the element at the $\text{K}^{th}$ place we can use multiple approach

1. sort the array and find the element at the $\text{K}^{th}$ index. But this will take $\text{O}(n\log{n})$ to sort the array.

2. we can create a min or max heap and then find the element

3. we can also use quick select algorithm to find in $\Theta(n)$

Solution 1 (using sorting)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

Solution 2 (using heap)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for ( int i = 0; i < nums.length; ++i) {
        minHeap.add(nums[i]);

        // to ensure we keep the K smallest element
        if (minHeap.size() > k) {
            minHeap.remove();
        }
    }

    return minHeap.peek();        
}