# Kth Largest Element in an Array — LC Medium

215. Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return the `kth` largest element in the array.

Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

You must solve it in `O(n)` time complexity.

Example 1:

Example 2:

Constraints:

• `1 <= k <= nums.length <= 105`
• `-104 <= nums[i] <= 104`

My first approach: using min heap as max heap

logic is quite straightforward, convert the min heap library to max heap and apply.

Time complexity: O(N + klogN)

Space complexity: O(1)

My second approach: using quickselect / quicksort algorithm

quite complicated, but the quicksort algorithm is as follows

lets say we have unsorted array such as: [5,3,5,7,2,3,5,8,9]

then ideally what we do is we pick a random element and call that as pivot.

then what we do is we iterate over the values and check if the value is smaller/larger than the pivot. as we are iterating, we keep a track of the pointer that tracks the index of the element that is larger than the pivot.

algorithm steps:

1. select pivot (rightmost)
2. left = 0, right = len(nums) -1, pointer = left
3. iterate over from the left to right, if we find elements that are less than the pivot, we swap the values of the nums[left] with nums[pointer]. and we move up a pointer
4. continue this till loop ends
5. when the loop is ended, we swap the pivot value with the last pointer position.
6. if the pointer position is less than len(nums) — k, do a recursion over step 1–5 of the right side of the pointer (since this means that the current pointer has not up to a level that is equal to the kth position)
7. if the pointer position is greater than len(nums) — k do a recursion over step 1–5 of the left side of the pointer
8. if the pointer position is equal to len(nums) — k, then return the element from nums with the index of p

code:

Time complexity: O(N) average case, worst case O(N²)

Space complexity: O(1)

--

--

## More from Paul Kang

Data Scientist, SWE + MLE