215. Kth Largest Element in an Array¶

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();        
}

Comments