Problem Statement
Find Kth Largest Element using Quickselect
You are given a list of numbers called nums and a number k. Your job is to find the kth largest number. "Kth largest" means: line the numbers up from biggest to smallest, then count k places in. So the 1st largest is the biggest number, the 2nd largest is the next one down, and so on. Note we count repeats too, so if the number 5 shows up twice, both copies count as separate spots. The easy way is to sort the whole list and grab the right spot, which takes O(n log n) time (that means the work grows a bit faster than the size of the list). But we can do better with a trick called Quickselect. Quickselect is like sorting, but lazy: it only does the sorting work near the one spot we actually care about and ignores the rest. On average this gives O(n) time, meaning the work grows in line with the size of the list, which is faster.
Signals to notice
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.
Trace it on nums=[3,2,1,5,6,4], k=2
target = 6 - 2 = 4 (need element at ascending index 4) quickselect(0,5): pivot=nums[5]=4 -> after scan store=3, swap pivot in -> nums=[3,2,1,4,6,5], pivot_idx=3 pivot_idx 3 != 4 and target 4 > 3 -> recurse RIGHT: quickselect(4,5) quickselect(4,5): pivot=nums[5]=5 -> 6>5 stays, swap pivot in -> nums=[3,2,1,4,5,6], pivot_idx=4 pivot_idx 4 == target 4 -> stop return nums[4] = 5
What must stay true
After partition, pivot is at final position. Only recurse into the side containing target index n-k.
Shape of the loop
target = n - k # kth largest = index target in ascending order
loop on [left, right]:
p = partition(left, right) # pivot lands at final sorted index p
if p == target: return nums[p]
elif target < p: right = p - 1 # recurse left side only
else: left = p + 1 # recurse right side onlyPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Worst case O(n²) — random pivot gives expected O(n).