Find Kth Largest Element using Quickselect
mediumTime: O(n)Space: O(1)
Recognize the pattern
kth largest without full sortpartition-based selectionexpected O(n)
Brute force idea
Sort and index — O(n log n).
Better approach
Quickselect: partition, recurse into one side only. Expected O(n). Use random pivot.
Key invariant
After partition, pivot is at final position. Only recurse into the side containing target index n-k.
Watch out for
Worst case O(n²) — random pivot gives expected O(n).