215. Kth Largest Element in an Array

Solution 1: Sort

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]

Time Complexity: O(N*Log(N)) // If we use TimSort (Python built-in) or quick sort
Space Complexity: O(1)

Solution 2: Max-Heap

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Bottom-up build max-heap
        for i in range(len(nums)): nums[i] *= -1
        heapq.heapify(nums)
        
        # Extract max for the kth max element
        for i in range(k - 1):
            heapq.heappop(nums)
        return -1 * heapq.heappop(nums)

Time Complexity: O(N + KLog(N)) // O(N) for bottom-up build heap + K times extract max
Space Complexity: O(N)

Solution 3: QuickSelect (Pivot) + Recursive

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
    
        # pivot = nums[0] # TLE in worst case
        pivot = random.choice(nums) # use random choice to speed-up the partition
        
        lftPart = [val for val in nums if val > pivot]
        midPart = [val for val in nums if val == pivot]
        rhtPart = [val for val in nums if val < pivot]

        L, M, R = len(lftPart), len(midPart), len(rhtPart)
        # The k th largest elmt in lftPart
        if k <= L:
            return self.findKthLargest(lftPart, k)
        # 1. (k == L + M) or 
        # 2. Duplicate pivot in midPart such that k in (L, L+M] partition
        elif (k > L) and k <= (L + M):
            return pivot
        # k > (L + M)
        else:
            return self.findKthLargest(rhtPart, k - L - M)

Time Complexity: O(N) // 不確定怎麼證明，可能要用 Amortize 估算
Space Complexity: O(N) // Worst case: we chose the min/max pivot, then we have to copy O(N) size array

Solution 4: QuickSelect (Pivot) + SWAP & Iterate

Time Complexity: O(N)
Space Complexity: O(1)

Solution 5: Binary Search

Time Complexity: O(K*Log(N)) // K is the kth largest
Space Complexity: O(1)

Reference

https://www.geeksforgeeks.org/find-second-largest-element-array/
https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/1019513/Python-QuickSelect-average-O(n)-explained
https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/