Quickselect
Partition around a pivot and recurse only into the side that contains the target rank.
SortingO(n) average, O(n^2) worstNew4 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
kth largest element
top k without full sort
median in linear time
The template
Get this into muscle memory, then adapt the condition per problem.
function select(lo: number, hi: number, k: number): number {
const p = partition(lo, hi);
if (p === k) return a[p];
return p < k ? select(p + 1, hi, k) : select(lo, p - 1, k);
} Watch QuickselectIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Sorting gives more than you need.
- 2Partitioning tells you the final index of the pivot.
- 3Randomise the pivot to avoid the adversarial worst case.
Drill it
Every problem in the bank that uses this pattern.
0 / 4 solved