Kth Largest Element in an Array


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

You may assume k is always valid, 1 ≤ k ≤ array's length.


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}
    return nums[len(nums)-k]


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{
        // 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]