import heapq
import random

# Approach 1: Min Heap of size k — O(n log k)
def find_kth_largest_heap(nums: list[int], k: int) -> int:
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

# Approach 2: QuickSelect — O(n) average
def find_kth_largest_select(nums: list[int], k: int) -> int:
    k = len(nums) - k  # convert to kth smallest

    def quick_select(left, right):
        pivot = nums[right]
        p = left
        for i in range(left, right):
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
        nums[p], nums[right] = nums[right], nums[p]

        if p > k:
            return quick_select(left, p - 1)
        elif p < k:
            return quick_select(p + 1, right)
        else:
            return nums[p]

    return quick_select(0, len(nums) - 1)
Sorting — When and Which

Sorting — When and Which

Sorting — When and Which
