Kth Largest Element in an Array


#1

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.


#2

Brute force. Sort the array, return the len(nums)-k element from the last.

Time Complexity - O(nlogn)

func findKthLargest(nums []int, k int) int {
    if len(nums)==0{return 0}
    sort.Ints(nums)
    return nums[len(nums)-k]
}

#3

The below algorithm uses Quick Select which does a partition until we find the kth largest element.

func findKthLargest(nums []int, k int) int {
    k = len(nums)-k // since we want the kth largest, leave as it is for kth smallest
    lo, hi := 0, len(nums)-1
    var res int
    for lo<=hi{
        res = partition(nums, lo, hi)
        if res==k{
            return nums[res]
        } else if res > k{
            hi = res-1
        } else {
            lo = res+1
        }
    }
    
    return res
} 

func partition(nums []int, start, end int) int {
    pivot := start
    for start<=end{
        // increase start until all elements at start are less than or equal to element at pivot
        for (start<=end && nums[start]<=nums[pivot]){ start++ }
        // decrement end until all ele at end are greater than ele at pivot
        for (start<=end && nums[pivot]<=nums[end]){ end-- }
        if start>end{
            break
        }
        // this puts them at their respective sorted place in comparision with pivot
        swap(nums, start, end)
    }
    // moving pivot to it's position, since this is where the partition breaks
    swap(nums, end, pivot)
    return end
}

func swap(nums []int, i, j int){
    nums[i], nums[j] = nums[j], nums[i]
}