Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array’s length.

[code lang="java"]
class Solution {
    public int findKthLargest(int[] nums, int k) {
        
    }
}
[code]

Idea – 1

Sort in non-increasing order and return the k-th element. Time and space complexity are that of a comparison based sorting. With traditional mergesort time is O(n\lg{n}) ans space is be O(n). With quicksort average time is O(n\lg{n}) and average space is O(lg{n}). With heapsort time is O(n\lg{n}) and space is O(1). 
[code lang="java"]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        Integer[] boxedArray = new Integer[n];
        for(int i = 0; i < n; ++i)
        {
            boxedArray[i] = nums[i];
        }
        
        Arrays.sort(boxedArray, (a, b) -> (b - a));
        
        return boxedArray[k-1];
    }
}
[code]

Runtime: 41 ms, faster than 11.26% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 38 MB, less than 62.44% of Java online submissions for Kth Largest Element in an Array.

Idea – 2

We use quickselect: repeatedly partition the array around a random pivot and go right or left based on the rank of the pivot. Average time O(n) and average space O(\lg{n}). Worst case time is O(n^2) and worst case space is O(n). 
[code lang="java"]
class Solution {
    
    private static final Random rng = new Random(System.currentTimeMillis() % Integer.MAX_VALUE);
    
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        return partition(nums, 0, n-1, k);
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
    
    private int partition(int[] A, int lo, int hi, int k)
    {
        int z = lo+rng.nextInt(hi-lo+1);
        int pivot = A[z];
        int i = lo-1, x = lo, j = hi;
        while(x <= j)
        {
            if(A[x] < pivot)
            {
                swap(A, ++i, x++);
            }
            else if(A[x] > pivot)
            {
                swap(A, x, j--);
            }
            else
            {
                ++x;
            }
        }
        
        // (i+1) is where pivot is right now
        int rank = A.length-(i+1);
        
        if(rank==k)
        {
            return pivot;
        }
        else if(rank < k)
        {
            return partition(A, lo, i, k);
        }
        else
        {
            return partition(A, i+2, hi, k);
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.81% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 35.6 MB, less than 97.57% of Java online submissions for Kth Largest Element in an Array.

Leave a comment