# Kth Largest Element in an Array — LC Medium

Companies: Facebook, Amazon, Spotify

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:**

**Input:** nums = [3,2,1,5,6,4], k = 2

**Output:** 5

**Example 2:**

**Input:** nums = [3,2,3,1,2,4,5,5,6], k = 4

**Output:** 4

**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.

`class Solution:`

def findKthLargest(self, nums: List[int], k: int) -> int:

# heap solution

nums = [-i for i in nums]

heapq.heapify(nums)

while k > 0:

ans = heapq.heappop(nums)

k -= 1

return -ans

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:

- select pivot (rightmost)
- left = 0, right = len(nums) -1, pointer = left
- 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
- continue this till loop ends
- when the loop is ended, we swap the pivot value with the last pointer position.
- 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)
- if the pointer position is greater than len(nums) — k do a recursion over step 1–5 of the left side of the pointer
- if the pointer position is equal to len(nums) — k, then return the element from nums with the index of p

code:

`# quickselect algorithm`

# if we are finding kth largest element, we know that such value will be there at len(nums) - k index position (i.e. len(nums) == 6, k == 2, [0,1,2,3, <4> ,5])

# [3,2,5,1,2,6,4]

# take 4 as pivot, (leave the value as it is if it is less than or equal to pivot)

# 3 is less than or equal to 4, swap it with i and p (which is its original position) and move the pointer by 1 (p = 1) [3,2,5,1,2,6,4]

# 2 is less than or equal to 4, swap it with i and p (which is its original position) and move the pointer by 1 (p = 2) [3,2,5,1,2,6,4]

# 5 is greater than 4, leave it [3,2,5,1,2,6,4]

# 1 is less than or equal to 4, swap it with i and p ([... 2,1,5,2...]) and move the pointer by 1 (p = 4) [3,2,1,5,2,6,4]

# 2 is less than or equal to 4, swap it with i and p ([... 2,1,2,5...]) and move the pointer by 1 (p = 5) [3,2,1,2,5,6,4]

# 6 is greater than 4, leave it

# at the end of iteration, swap the p pointer with the pivot [3,2,1,2,4,6,5]

# if p > k, then recurse this process on the right side of pivot

# elif p < k, then recurse this process on the left side of pivot

# else p == k, then return the value of the pivot

class Solution:

def findKthLargest(self, nums: List[int], k: int) -> int:

# redefine k

k = len(nums) - k

def quickSelect(left, right):

p = left

pivot = nums[right]

for i in range(left, right):

if nums[i] <= pivot:

# swap the pointer with the current iterations

nums[p], nums[i] = nums[i], nums[p]

p += 1

# swap the pivots

nums[p], nums[right] = pivot, nums[p]

# search right

if p < k: return quickSelect(p + 1, right)

elif p > k: return quickSelect(left, p - 1)

else: return nums[p]

return quickSelect(0, len(nums) - 1)

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

Space complexity: O(1)