The problem
Return the kth largest element (in sorted order, not distinct) without fully sorting the array.
Stuck? Reveal hints one at a time
How to approach it
- 1Target index = n − k in ascending order.
- 2Partition around a RANDOM pivot: elements < pivot left, > pivot right.
- 3If the pivot lands on the target index, done. Otherwise recurse into the single side containing it.
- 4Each round discards a fraction of the array — geometric series sums to O(n).
Key insight
Quickselect is quicksort minus the recursion into the "wrong" half — sorting the parts you never ask about is wasted work.
The solution
Watch out for
- Random pivots are mandatory — fixed pivots go quadratic on the judge’s sorted inputs.
- kth LARGEST = index n − k ascending; flipping that sign returns the kth smallest.