[LeetCode] 215. Kth Largest Element in an Array

Problem : https://leetcode.com/problems/kth-largest-element-in-an-array/

A naive solution : 

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

Use heap:

Time complexity = O ( N Log K )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        while len(nums) > k:
            heapq.heappop(nums)
        
        return nums[0]

In real interview, I assume it expects to be resolved by Quick Sort.

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:  
        def swap(left, right):
            nums[left], nums[right] = nums[right], nums[left]
            
        def partition(left, right):
            pivot = left
            
            while left <= right:
                if nums[pivot] <= nums[left]:
                    left += 1
                elif nums[pivot] >= nums[right]:
                    right -= 1
                else:
                    swap(left, right)
                
            swap(left-1, pivot)
            return left-1
                
        def qsort(left, right):
            while left <= right:
                pivot = partition(left, right)
            
                if pivot == k - 1: 
                    return nums[pivot]
                elif pivot > k - 1:
                    right = pivot - 1
                else:
                    left = pivot + 1
        
            return nums[right]
        
        return qsort(0, len(nums)-1)