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]
}
``````