Find Kth Largest Element using Quickselect
mediumTime: O(n)Space: O(1)
Signals to notice
kth largest without full sortpartition-based selectionexpected O(n)
Brute force first
Sort and index — O(n log n).
The key insight
Quickselect: partition, recurse into one side only. Expected O(n). Use random pivot.
What must stay true
After partition, pivot is at final position. Only recurse into the side containing target index n-k.
Easy way to go wrong
Worst case O(n²) — random pivot gives expected O(n).