Problem. Given an integer array nums and k, return the k-th largest element (in sorted order, not the k-th
distinct).
nums = [3, 2, 1, 5, 6, 4], k = 2 → 5
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → 4
Sorting answers it, but sorts n − 1 elements you don't care about. The two classic improvements trade in different directions: a heap of size k uses little memory and works on streams; quickselect is linear on average but needs the whole array in memory.
ML context. "The k-th largest score" is a threshold: keep the top 1% of candidates by relevance, the 95th
percentile of latencies, the cutoff for top-k sampling over logits, the score above which a classifier flags the k
highest-risk cases. PyTorch's torch.topk and NumPy's np.partition implement exactly the two ideas here.