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 Kth\text{K}^{th} place we can use multiple approach

  1. sort the array and find the element at the Kth\text{K}^{th} index. But this will take O(nlogn)\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 Θ(n)\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();        
}

Last updated