Quickselect
Why Quickselect exists — the story
You're an engineer at Netflix. The Recommendation Systems team asks: "For each user, return the top 10 movies from our catalog of 100,000 titles."
The obvious approach: sort all 100,000 movies by predicted rating, return the first 10. O(n log n) — for 200 million users, ~2·10¹² sort operations. Manageable, but wasteful. You spent effort ranking movie 50,000 vs movie 60,000 when you only care about the top 10.
You could argue: "sort is O(n log n), that's fine." And it is — for one query. But Netflix does this per user, per day, for 200 million users. And the interesting question isn't sort; it's "why did I spend cycles ordering movies I'll never return?" After finding the top 10, you don't care whether movie 50,000 or 60,000 is better. That's pure waste.
The pattern is Quickselect: return the k-th smallest (or largest) element in O(n) expected time without fully sorting. Pick a pivot, partition the array around it. The pivot lands in its final sorted position p. If p == k, you're done. If p < k, the answer is in the right half — throw away the left half and recurse. If p > k, symmetric. You never recurse into both halves. For finding top-10-of-100,000, Quickselect averages ~200,000 ops vs. sort's 100,000 · log₂(100,000) = 1,700,000 — an 8.5× speedup for the same answer. Scaled to Netflix: from 2·10¹² to 2·10¹¹ ops per day. Ships hit datacenter power budgets.
Quickselect borrows the partition step from quicksort. Pick a pivot, move smaller values to the left and larger values to the right, then the pivot lands in its final sorted position. If that position is the target rank, you are done. If it is too small, the target is on the right; if it is too large, the target is on the left. Unlike quicksort, you never recursively sort both sides. You throw away the side that cannot contain the answer.
Grokking arc: The motivating problem is finding one rank without needing the whole sorted order. Brute force sorts everything. Can we do better? Partition once, compare the pivot's final index with the target rank, and discard the side that cannot contain the answer.
Sorting is a powerful habit, but sometimes it is too much. If someone asks for the 2nd largest number in [3,2,1,5,6,4], a full sort gives [1,2,3,4,5,6] and then returns 5. Correct, but notice how much extra information you computed: you learned the full order of every value even though only one rank mattered. Quickselect exists for the moment you say, "I only need the element that would land at one index if the array were sorted."
Trace a tiny example by hand. For [7, 1, 5, 3, 9, 2], the 2nd largest is index n-k = 4 in ascending order. Suppose pivot 5 partitions to [1,3,2,5,9,7], so pivot index is 3. Target 4 is to the right, so ignore indices 0..3. Now partition [9,7]; if pivot 7 lands at index 4, return 7. You selected the answer without sorting [1,3,2] at all.
After partitioning around a pivot, the pivot sits at its final sorted index p. If p == k you're done. If p < k, the answer is in the right half; else the left. You never touch the side that doesn't contain rank k.
Key Insight — Quickselect is expected O(n) because it discards half the array on each step. Total work: n + n/2 + n/4 + ... = 2n = O(n). This is the same geometric-series argument as binary search, but applied to a partition step instead of a midpoint comparison. Say "expected linear" out loud in interviews — the word "expected" acknowledges the worst-case O(n²).
Lomuto is simpler (one pass, one write-pointer) but 3× slower in practice and has worst-case O(n²) even on unique-value arrays. Hoare's two-pointer swap is 3× faster and handles equal elements better. For interviews: use Lomuto for correctness (simpler to explain); for contests: use Hoare.
Once partition() returns index p, a[p] is the correct value for rank p in the fully-sorted output. Quickselect never re-partitions across p because the search is confined to the side that could contain rank k.
Every recursive call maintains this: if p < k, recurse on [p+1, hi] (which contains k); if p > k, recurse on [lo, p-1]. Violating this invariant means you passed the wrong subrange and will return the wrong rank.
When to use it — one-shot rank selection
Recognize by
- "find the kth smallest" or "find the kth largest" in an unsorted array
- "find the median" when you do not need the full sorted array
- "return the kth order statistic" or "element at rank r"
- "top k" when returning the k items in any order is okay and mutating/partitioning is allowed
- constraints where O(n log n) sort is acceptable but the interviewer asks for better average time
- array is available in memory, so random access and in-place swaps are allowed
Picking the first or last element as pivot on already-sorted input → each partition shrinks by 1 → O(n²). Rule: pivotIdx = lo + random.nextInt(hi - lo + 1). For truly deterministic linear-time worst case, use median-of-medians (Blum-Floyd-Pratt-Rivest-Tarjan 1973) — but mention only if asked.
Quickselect's recursion depth is expected O(log n) but worst case O(n). On adversarial input with n = 10⁵, that's 10⁵ stack frames = stack overflow. Iterative Quickselect uses a while loop and eliminates the recursion; use this on very large inputs.
When NOT to use it
You need k-th in a stream (no random access) — use a heap. You need the k boundary items in order — use a heap or partial sort. Adversarial inputs with the same pivot every time degrade to O(n²) — always pick a random pivot or use median-of-medians.
Do not reach for Quickselect when the input must remain in original order and mutation is forbidden unless you are willing to copy the array. Do not use it for repeated queries on the same data; sorting once or building an order-statistics structure may win. And if the problem requires stable ordering, tie-aware output, or all top-k values sorted, Quickselect alone only gets you the boundary; you still need post-processing.
How to use it — template
int target = rankIndex; // 0-based index in sorted order
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int pivotIdx = choosePivot(lo, hi);
int p = partition(a, lo, hi, pivotIdx);
if (p == target) {
return a[p];
} else if (p < target) {
lo = p + 1;
} else {
hi = p - 1;
}
}
return a[lo];The template is a narrowing search over ranks, not values. partition gives you one value in its final sorted position. Comparing that position with target tells you which half can still contain the answer. choosePivot should be randomized or at least not always the same bad endpoint. For kth largest, convert to an ascending rank with target = n - k; for kth smallest, use target = k - 1.
History — Hoare 1961, Blum-Floyd-Pratt-Rivest-Tarjan 1973
Quickselect was invented by Sir Charles Antony Richard Hoare in 1961 — the same year and the same paper ("Algorithm 65: FIND", Communications of the ACM 4(7):321-322) that introduced quicksort. Hoare was 27 years old, working on a Russian-English translation dictionary at Elliott Brothers Ltd; sorting Russian words prompted him to invent the partition technique. He got the Turing Award in 1980 for both algorithms.
Hoare's quickselect had a randomized average of O(n) but worst-case O(n²) on adversarial input. This worst case was unacceptable in system code (adversaries could craft slow requests to DoS a server). The question of "can we achieve deterministic linear-time selection?" stayed open for 12 years.
Blum, Floyd, Pratt, Rivest, and Tarjan answered in 1973 with the median-of-medians algorithm — a deterministic O(n) selection algorithm. Their trick: recursively find a "good enough" pivot by taking the median of medians of groups of 5. This guarantees the pivot rejects at least 30% of the elements per step, giving O(n) with a large constant. The paper "Time bounds for selection" is one of the most cited results in theoretical computer science.
Real-world adoption:
- C++
std::nth_element— introselect (Musser 1997), a hybrid of Hoare's quickselect and heapsort-fallback for worst-case protection. - NumPy's
np.partition— uses the same introselect hybrid. - Netflix's recommendation top-K — the scene we opened with; production code uses quickselect for O(n) expected instead of O(n log n) sort.
- Databases — every "TOP N" query optimizer uses partial partitioning under the hood, not full sort.
- Median filters in image processing (used for denoising every phone photo) — quickselect over pixel windows.
- Java's Dual-Pivot Quicksort (Yaroslavskiy 2009), the algorithm behind
Arrays.sorton primitives, uses two pivots per partition; quickselect variants adapt the same idea.
Bloch's 2006 blog post on the Binary Search bug also revealed that Java's original Arrays.sort had subtle quickselect-related bugs — even the JDK's sort spec-authors weren't immune. That story reinforces the Chapter 27 point: partition-based algorithms look simple but are among the most bug-prone code in a standard library.
When you tell an interviewer "Hoare's quickselect, expected O(n) with randomized pivot, worst-case O(n²) unless you use median-of-medians for a guaranteed O(n)," you're citing a 63-year-old lineage still running at the bottom of every ML framework and every database's top-K operator.
Quickselect (Kth Largest Element) Medium
↗ LeetCode: Kth Largest Element in an Array
Problem
Find the kth largest element in an unsorted array (a one-shot query) — faster than fully sorting.
Constraints: 1 ≤ k ≤ n ≤ 10⁵; expected O(n) average via partitioning.
Example 1: [3,2,1,5,6,4], k = 2 → 5.
Example 2: [3,2,3,1,2,4,5,5,6], k = 4 → 4.
Solution — brute force
The baseline is to sort the array and index into the sorted result.
sort nums ascending
return nums[nums.length - k]That is O(n log n) time and O(1) or O(n) extra space depending on the language and whether you can mutate the input. It is also the best first sentence in an interview because it proves you understand that "kth largest" means a rank, not necessarily a distinct value. Quickselect improves the average runtime by avoiding the side of the partition that cannot contain that rank.
A heap baseline is also possible: keep a min-heap of size k and return its root after scanning all values. That costs O(n log k) and works for streams. Quickselect is usually preferred for one in-memory one-shot query because expected O(n) is better.
Baseline complexity: O(n log n) time; O(1) or O(n) extra space depending on sorting/copying.
Solution — optimized
The optimized solution keeps the original Java intact and explains the pattern that removes the brute-force bottleneck.
Pattern
Partition around a (randomized) pivot; recurse only into the side that contains rank k.
After partition, the pivot rests at its final sorted position p; everything left ≤ pivot ≤ everything right. Compare p to the target index to pick the side.
Java
int findKthLargest(int[] a, int k) {
int target = a.length - k; // kth largest = index n-k ascending
int lo = 0, hi = a.length - 1;
Random rnd = new Random();
while (lo < hi) {
int p = partition(a, lo, hi, lo + rnd.nextInt(hi - lo + 1));
if (p == target) break;
else if (p < target) lo = p + 1;
else hi = p - 1;
}
return a[target];
}
int partition(int[] a, int lo, int hi, int pivotIdx) {
int pivot = a[pivotIdx];
swap(a, pivotIdx, hi); // stash pivot at end
int store = lo;
for (int i = lo; i < hi; i++)
if (a[i] < pivot) swap(a, store++, i);
swap(a, store, hi); // pivot to final place
return store;
}
void swap(int[] a, int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }One possible randomized run for [3,2,1,5,6,4], k=2; target index is 6-2=4 in ascending order.
Rank conversion: kth largest vs kth smallest
Most bugs in this problem are off-by-one rank bugs. If the array were sorted ascending, the 1st smallest is index 0, so kth smallest is k - 1. The 1st largest is the final index n - 1, so kth largest is n - k. For [1,2,3,4,5,6], the 2nd largest is 5, which sits at index 4; n-k = 6-2 = 4. Say this conversion out loud before writing the loop.
Duplicates do not change the formula. In [3,2,3,1,2,4,5,5,6], sorted ascending is [1,2,2,3,3,4,5,5,6]. The 4th largest is index 9-4=5, value 4. You are selecting by position after sorting, not by distinct value.
Partition mechanics in plain English
The partition helper temporarily moves the pivot to the end. store marks the first index where a value >= pivot may belong. As you scan from lo to hi-1, every value smaller than pivot gets swapped to store, and store advances. At the end, swapping the pivot into store places it after all smaller values and before all larger-or-equal values. That is enough for selection; the left side does not need to be internally sorted.
Using < pivot instead of <= pivot means duplicates equal to the pivot collect on the right side. That is valid for selection because the pivot still lands at one sorted-compatible position. On arrays with many equal values, three-way partitioning (<, =, >) can be faster, but the two-way version is the standard compact interview solution.
Mutability and return shape
Quickselect rearranges the array. It does not sort it, but it absolutely mutates it. That is fine for most LeetCode problems because the input array is not reused after the call. In a production API, you should either document the mutation or copy the array first. Copying preserves the caller's data but changes the space complexity to O(n). In an interview, mention this trade-off if the prompt says "do not modify the input."
Also distinguish between returning the kth value and returning the top k values. The provided code returns one integer. If the prompt asks for the k largest elements in any order, Quickselect can partition until index n-k is in place, and then the suffix from n-k to n-1 contains the k largest elements, not necessarily sorted. If the prompt asks for those k elements sorted, you either sort just that suffix or use a heap / full sort depending on constraints.
Pivot quality and randomness
The partition logic is deterministic once a pivot index is chosen. The randomness is only there to protect you from consistently bad pivots. On already sorted input, always choosing the last element is disastrous for kth largest: the pivot lands at the end, then the next end, then the next, shrinking by one each time. Random choice makes that pattern extremely unlikely.
If randomization is not allowed, median-of-three is a practical compromise: compare the first, middle, and last values and use their median as the pivot. The theoretical worst-case linear solution is median-of-medians, but it is longer and rarely expected in a standard interview unless the prompt explicitly demands deterministic O(n). Most interviewers are satisfied when you name the worst case and use randomized pivoting.
Duplicates and three-way partitioning
The two-way partition above works with duplicates, but it may do extra work when the array contains many values equal to the pivot. For example, if every value is 5, a two-way partition may place the pivot at the start of the active range repeatedly. A three-way partition groups values into < pivot, == pivot, and > pivot. Then if the target rank falls inside the equal band, you can return immediately.
You do not need to implement three-way partitioning unless the interviewer pushes on duplicate-heavy inputs. The key is to understand that duplicates do not make the answer ambiguous: kth largest is still a position in sorted order. If several equal values occupy that region, returning that value is correct.
Testing checklist
Use these mental tests to catch rank and partition mistakes:
| Input | k | Expected | Lesson |
|---|---|---|---|
[3,2,1,5,6,4] | 2 | 5 | target is n-k, not k |
[1] | 1 | 1 | loop may never run; return target value |
[3,3,3,3] | 2 | 3 | duplicates are ranks too |
[2,1] | 1 | 2 | kth largest means largest when k is 1 |
[2,1] | 2 | 1 | smallest is also kth largest when k equals n |
How to narrate partition during a dry run
When tracing Quickselect, do not try to fully sort the active range on paper. Say which pivot you chose, draw a vertical bar at its final index after partition, and compare that index to the target. Everything left of the bar is "small enough," everything right is "large enough," but their internal order is irrelevant. This keeps the trace short and reinforces the reason Quickselect is faster than quicksort.
For the example [3,2,1,5,6,4], if pivot 4 lands at index 3, you can immediately say: "The target is index 4, so every value at index 0 through 3 is too low-ranked to matter now." That is the core optimization. Each round should delete a range from consideration.
Same pattern, new tweaks
"Partition around a pivot and recurse into only one side" selects without fully sorting:
| Variation | The one thing that changes | Time |
|---|---|---|
| Kth Largest Element | the target index is n-k in ascending order | O(n) avg |
| K Closest Points to Origin | partition by squared distance; after selection, the first k positions hold the closest points in any order | O(n) avg |
| Top K Frequent Elements | quickselect over distinct values using frequency as the partition key | O(n) avg |
| Wiggle Sort II | quickselect the median, then place larger/smaller halves into virtual indices | O(n) avg |
| Median of an Unsorted Array | select index n/2 (and maybe n/2 - 1 for even length) instead of sorting | O(n) avg |
Bad pivots. Example: nums=[1,2,3,4,5], k=1, picking the last element as pivot every time → each partition shrinks by only 1 → O(n²). Random pivot (or median-of-three) keeps average O(n).
First, I'd translate kth largest into an ascending target index: n-k, so duplicates are handled naturally by rank. The brute force is sorting in O(n log n), and a heap gives O(n log k), especially for streams. Since this is a one-shot array query, I'll use Quickselect: partition around a randomized pivot and continue only on the side containing the target index. The expected time is O(n), worst-case O(n²) with unlucky pivots, and space is O(1) in-place.
For a stream or repeated queries, a size-k heap (O(n log k)) beats one-shot Quickselect. Quickselect also drives Wiggle Sort II and median-of-medians selection.
Time Complexity
Time O(n) average, O(n²) worst · Space O(1).
The average is linear because a random pivot tends to discard a meaningful fraction of the remaining range. The worst case happens when each pivot is the smallest or largest remaining element, so the active range shrinks by only one each time. This implementation is iterative, so it avoids recursion stack space.
O(n) expected with randomized pivots; O(n²) worst case if pivots are consistently bad.
Space Complexity
O(1) extra because the selection loop partitions in place.
Learning notes
- Why
target = a.length - k? — kth largest is then-kindex in ascending sorted order. - Why choose a random pivot? — it avoids repeatedly picking the smallest/largest element on sorted or adversarial inputs.
- Why move the pivot to
hi? — it frees the scan range and makes the final swap simple. - Why
storeadvances only for< pivot? — it partitions smaller values to the left and leaves greater/equal values to the right. - Why discard one side after partition? — the pivot's final rank tells which side can still contain the target.
- Why return
a[target]? — once the loop narrows or hits the target, that index holds the selected rank.