Solutions

# Sorting, heap, quickselect
# heap

# Sorting - O(n log n) time, O(n) space
def findKthLargest1(nums: list[int], k: int) -> int:
    nums.sort()
    return nums[-k]
    
# Heap - O(n log k) time, O(k) space
def findKthLargest2(nums: list[int], k: int) -> int:
    import heapq

    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            # Remove the lowest number
            heapq.heappop(heap)
    # At this point the heap has the k largest number
    # so we just return the lowest of the heap
    return heapq.heappop(heap)

# Heap - O(n log k) time, O(k) space
def findKthLargest(nums: list[int], k: int) -> int:
    import heapq
    return heapq.nlargest(k, nums)[-1]

# Quickselect - O(n) average time, O(n^2) worst-case time, O(n) space
def findKthLargest(nums: list[int], k: int) -> int:
    # convert k to its zero-based sorted index
    k = len(nums) - k

    def quickselect(l: int, r: int):
        # choose a pivot randomly (common: rightmost index)
        pivot, p = nums[r], l
        for i in range(l, r):
            # move to the left all numbers less than pivot
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
        # move pivot to its final place
        nums[p], nums[r] = nums[r], nums[p]

        # If pivote is not in its final place,
        # recursively call quickselect on the left or right side of the pivot
        if p > k:
            return quickselect(l, p-1)
        elif p < k:
            return quickselect(p+1, r)
        else:
            return nums[p]

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