Kth Largest Element in an Array — Interview Guide

• A min-heap of size k holds the k largest seen; the root is the answer. O(n log k).
• Quickselect partitions around a pivot and recurses into the side containing the k-th index. Expected O(n).
• Quickselect's worst case is O(n²); randomize the pivot or use median-of-medians to avoid it.

import random
def find_kth_largest(nums, k):
    k = len(nums) - k
    def qs(l, r):
        piv = random.randint(l, r)
        nums[piv], nums[r] = nums[r], nums[piv]
        p = l
        for i in range(l, r):
            if nums[i] < nums[r]:
                nums[i], nums[p] = nums[p], nums[i]; p += 1
        nums[p], nums[r] = nums[r], nums[p]
        if p == k: return nums[p]
        return qs(l, p - 1) if p > k else qs(p + 1, r)
    return qs(0, len(nums) - 1)

• Find the k-th smallest instead.
• Stream version: maintain a heap over an unbounded input.
• Return the top-k elements in sorted order (heap then extract).