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:

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:

# 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)