Quickselect, Median of Medians & Order Statistics
The -th order statistic of a collection is the element that would sit at index if you sorted it. The minimum is the 0th order statistic (0-indexed), the maximum is the -th, the median is the one in the middle, and "the 99th-percentile latency" is the order statistic at rank . Selection is the problem of finding it. The obvious method is to sort and index, which costs . This lesson is about the surprising fact that you do not have to: selection is strictly easier than sorting, and can be done in time, deterministically, in the worst case.
This is the last technique lesson of Module 2. It reuses the partition step from Quick Sort, the heap from Heaps & Priority Queues, and the recurrence-solving tools from Complexity Analysis.
Why this exists
You need order statistics far more often than you need a fully sorted array. A monitoring system wants p50, p95 and p99 latency, not the whole sorted list of ten million request times. A recommendation service wants the top 20 items out of a million scored candidates. A k-d tree splits its points at the median coordinate at every level. A robust estimator replaces the mean with the median because one corrupted reading cannot move the median far. In each case sorting does far more work than the question asks for: it pins down the relative order of every pair of elements, when you only care about one position.
The history is short and remarkable. In 1961 C. A. R. Hoare published FIND (Algorithm 65 in Communications of the ACM) alongside Quicksort (Algorithm 64): partition around a pivot, then continue only into the side that contains the wanted rank. That is quickselect, and on random pivots it runs in expected linear time. Whether selection could be done in worst-case linear time stayed open until 1973, when Manuel Blum, Robert Floyd, Vaughan Pratt, Ron Rivest and Robert Tarjan — four future Turing Award winners among five authors — published "Time bounds for selection" (Journal of Computer and System Sciences 7(4), 1973). Their pivot rule, median of medians, guarantees a pivot good enough that the recursion shrinks geometrically no matter what the input is. Two years later Floyd and Rivest published a sampling-based algorithm that is much faster in practice, and in 1997 David Musser's introselect combined quickselect's speed with a worst-case safety net, which is the shape of std::nth_element today.
Selection has a cousin that appears constantly in interviews: top-. For a fixed array it is selection plus a filter; for a stream it is a heap of size ; for a set that changes between rank queries it is an order-statistic tree, a balanced BST whose nodes know their subtree sizes.
Pattern triggers
| If the problem says… / has… | Think of | Why |
|---|---|---|
| "-th largest", "-th smallest", "median", "the element at rank " in a static array | Quickselect (expected ) or nth_element | Only one position matters, so discard the side that cannot contain it |
| "top ", " closest", " most frequent" and | Heap of size () or quickselect + filter () | You need a set of items, not their order |
| "stream", "online", "cannot store everything", "return top at any time" | Bounded min-heap of size | Constant memory per answer slot; each new item is one comparison against the heap root |
| "running median", "median of a sliding window" | Two heaps or an order-statistic structure | The median changes by one rank per insert or delete |
| "guaranteed worst case", "adversarial input", "real-time" | Median of medians or introselect | Random pivots have an tail; a deterministic pivot rule removes it |
| "minimise the sum of distances", "best meeting point", "post office location" | (Weighted) median | The sum of absolute deviations is minimised at the median |
| "-th smallest pair / sum / fraction / distance" over an implicit set of size | Binary search on the answer + counting | You cannot materialise items; count how many are instead |
| "rank of ", "how many elements are less than ", with inserts and deletes | Order-statistic tree or Fenwick tree over compressed values | Each node stores subtree size, so rank and select are |
| "approximate p99 over billions of events" | Quantile sketch (t-digest, KLL) | Exact selection needs all the data; a sketch needs kilobytes |
The decisive question is almost always: is the data static, streaming, or dynamic? Static means quickselect; streaming means a heap; dynamic with repeated rank queries means a tree.
Intuition & first principles
Start with the one fact that powers everything here. After a partition around pivot , the pivot sits at its final sorted index. Everything to its left is and everything to its right is , so if the pivot landed at index , then is the -th order statistic. You do not know the order inside either side, and you do not need to.
Now compare with the rank you want:
- If , you are done.
- If , the answer is among the elements on the left; the right side is irrelevant forever.
- If , the answer is on the right, at rank within the whole array (or rank within the right part, if you re-index).
Quicksort recurses into both sides. Quickselect recurses into one. That single change turns ( levels of work each) into when pivots split evenly. The whole game of this lesson is: how do you make sure the split is even enough, often enough?
There are three answers, in increasing order of guarantee and decreasing order of practical speed:
- Pick the pivot at random. Most pivots are decent. Bad ones are rare and do not compound. Expected time is linear; the worst case is quadratic but astronomically unlikely.
- Pick the pivot by sampling. Floyd–Rivest takes a small random sample, recursively finds two elements of the sample that bracket the target rank with high probability, and partitions around both. Almost every element is compared about once.
- Pick the pivot by computing a near-median deterministically. Median of medians spends a constant fraction of the work finding a pivot that is guaranteed to have at least about 30% of the elements on each side. The recursion shrinks by a constant factor every round, so the worst case is linear.
An analogy: to find the 50th-shortest of 1,000 people, pick someone and split the crowd into shorter and taller. If 300 are shorter, the person you want is among them and the other 700 can go home. You never sort anyone.
Mechanics
Quickselect
flowchart TD
S["select(a, lo, hi, k)"] --> P["choose pivot in a[lo..hi]<br/>(random)"]
P --> Q["partition: smaller left,<br/>pivot at index j, larger right"]
Q --> C{"compare j with k"}
C -->|"j == k"| F["return a[k]"]
C -->|"j > k"| L["hi = j - 1<br/>(discard right side)"]
C -->|"j < k"| R["lo = j + 1<br/>(discard left side)"]
L --> P
R --> P
The loop maintains one invariant: the answer is in a[lo..hi], at absolute index k. Elements outside the window are already in their final relative position with respect to it: everything left of lo is everything in the window, everything right of hi is it. Because is an absolute index, you never re-index; you just narrow the window.
Trace: quickselect by hand
a = [3, 8, 1, 9, 4, 7, 2, 6, 5], find the element at sorted index k = 6 (the 7th smallest; the answer is 7). To make the trace reproducible we use the last element as the pivot and the Lomuto partition (elements strictly less than the pivot move left). Computed by script.
| Round | lo | hi | window before | pivot | array after partition | pivot index j | decision |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 8 | [3, 8, 1, 9, 4, 7, 2, 6, 5] | 5 | [3, 1, 4, 2, 5, 7, 9, 6, 8] | 4 | : lo = 5 |
| 2 | 5 | 8 | [7, 9, 6, 8] | 8 | [3, 1, 4, 2, 5, 7, 6, 8, 9] | 7 | : hi = 6 |
| 3 | 5 | 6 | [7, 6] | 6 | [3, 1, 4, 2, 5, 6, 7, 8, 9] | 5 | : lo = 6 |
| 4 | 6 | 6 | [7] | 7 | [3, 1, 4, 2, 5, 6, 7, 8, 9] | 6 | : return 7 |
Count the comparisons: . Sorting nine elements with merge sort takes about 20. The left part [3, 1, 4, 2] stays unsorted. Quickselect leaves the array partitioned around index , which is exactly the contract of C++'s std::nth_element: a[k] is correct, everything before it is it, everything after is it.
If the array had been [7, 2, 9, 4, 3, 8, 1, 6, 5] with k = 4, the very first pivot (5) would have landed at index 4 and the algorithm would have stopped after 8 comparisons. Quickselect's running time depends heavily on luck, which is why we need the analysis below.
Median of medians
flowchart LR
A["n elements"] --> G["split into groups of 5<br/>(last group may be smaller)"]
G --> M["median of each group<br/>(constant work per group)"]
M --> R["recursively select the median<br/>of the n/5 medians: pivot x"]
R --> P["partition all n elements around x"]
P --> D{"rank of x vs k"}
D -->|"equal"| F["return x"]
D -->|"k smaller"| L["recurse on the less-than side<br/>at most 7n/10 + 6 elements"]
D -->|"k larger"| H["recurse on the greater-than side<br/>at most 7n/10 + 6 elements"]
Median of medians changes only the pivot rule. It is two recursive calls: one on the medians to choose the pivot, and one on the surviving side after partitioning.
Here is one round on 25 distinct numbers (computed by script):
| Group | Elements | Sorted | Median |
|---|---|---|---|
| 1 | 42, 20, 51, 84, 7 | 7, 20, 42, 51, 84 | 42 |
| 2 | 10, 69, 13, 47, 75 | 10, 13, 47, 69, 75 | 47 |
| 3 | 8, 65, 28, 5, 12 | 5, 8, 12, 28, 65 | 12 |
| 4 | 56, 54, 9, 31, 85 | 9, 31, 54, 56, 85 | 54 |
| 5 | 71, 55, 89, 73, 16 | 16, 55, 71, 73, 89 | 71 |
The medians are 42, 47, 12, 54, 71; their median is 47, which becomes the pivot. Here 47 happens to be the exact median of all 25 numbers (12 smaller, 12 larger), but the algorithm only promises something weaker, and the promise is what matters. Look at the groups whose median is (groups 2, 4 and 5). In each, the median and the two elements above it are : that is elements guaranteed to be without examining their values any further. By symmetry at least 9 are . So no matter how the numbers were arranged, at most elements survive into the next round.
The ladder: brute force → better → optimal
Rung 1: sort, then index —
Sort a copy and return sorted(a)[k]. Two lines in any language, impossible to get wrong, and the right answer when is small, when you will ask many rank queries on the same data (sort once, then each query is ), or when you need the top in order anyway. The cost is all the comparisons spent ordering pairs you never look at: about of them. For that is roughly 20 million comparisons to learn one number.
Rung 2: a heap of size —
To find the -th largest, keep a min-heap of the largest elements seen so far. Its root is the smallest of them, which is the current candidate for the answer. For each new element : if the heap has fewer than items, push ; otherwise, if beats the root, replace the root with and sift down. After the pass, the root is the -th largest and the heap holds the top .
Each operation costs , so the total is time and space. Two properties make this rung more important than its complexity suggests:
- It is online: it never needs to see the whole input at once, so it works on streams and on data too large for memory.
- On random input it is much cheaper than the bound. Element (1-indexed) enters the heap only if it is among the largest of the first , which happens with probability , so the expected number of replacements is about . For and that predicts 691; our simulation counted 700. Almost every element costs one comparison against the root and nothing more.
A variant heapifies all elements in and pops times: , not online.
Rung 3: quickselect — expected, worst
Partition and recurse into one side, as above. With a uniformly random pivot, the expected number of comparisons to find the median is about , and to find the minimum about (Knuth's exact analysis of Hoare's FIND). We checked this by simulation: over 4,000 runs at the averages were for the median and for the minimum, matching the formula's and within sampling noise. The worst case is comparisons, when every pivot happens to be an extreme; with random pivots the probability of anything close to that is exponentially small, but with a fixed rule like "last element" an adversary (or simply already-sorted data) triggers it every time.
Rung 4: median of medians — worst case
Choose the pivot as the median of group medians, as above. The guarantee that at least about elements lie on each side makes the recursion , which solves to (proved in the next section). The constant is large: the simple implementation does several times more work than random quickselect. In practice, median of medians is used as a fallback (introselect) or as a pivot rule for quicksort when a hard worst-case bound is required, not as the primary algorithm.
Rung 5: introselect and Floyd–Rivest — fast and safe
Introselect runs quickselect with a cheap pivot rule, counts how much progress it makes, and switches to a guaranteed-linear method if progress stalls. You get quickselect's constants on normal inputs and a worst-case bound on adversarial ones. Floyd–Rivest uses random sampling to choose two pivots that tightly bracket rank , so the window shrinks to after a single pass; its expected comparison count is , about for the median, which is essentially optimal for random-pivot methods.
Comparison
| Method | Time (expected) | Time (worst) | Extra space | Online? | Leaves | Use when |
|---|---|---|---|---|---|---|
| Sort + index | – | No | fully sorted array | small , many queries, or top- needed in order | ||
| Min-heap of size | Yes | the top in a heap | streams, , data larger than memory | |||
| Randomized quickselect | , ~ comparisons for the median | iterative | No | array partitioned at | default for a static array | |
| Median of medians | recursion | No | partitioned at | hard real-time or adversarial input, or as a fallback | ||
| Introselect | with MoM fallback, with heap fallback | No | partitioned at | library implementations (nth_element, numpy.partition) | ||
| Floyd–Rivest | , ~ comparisons for the median | (vanishingly unlikely) | No | partitioned at | very large arrays where comparisons are expensive |
Correctness
Quickselect
Invariant. At the top of each loop iteration, lo <= k <= hi, and the multiset in a[lo..hi] is exactly the set of elements whose rank (in the sorted original) lies in [lo, hi]. Equivalently: every element left of lo is every element in the window, and every element right of hi is every element in the window.
Initialisation. lo = 0, hi = n - 1: the window is the whole array and by precondition.
Maintenance. Partitioning a[lo..hi] around pivot places at index with everything in a[lo..j-1] and everything in a[j+1..hi] . Combined with the invariant, a[j] is exactly the element of rank in the whole array (there are elements to its left, all no larger). If , the element of rank is among a[lo..j-1], and every element we drop (a[j..hi]) is all elements we keep, so setting hi = j - 1 preserves the invariant. Symmetrically for .
Termination. Each iteration either returns or strictly shrinks the window (the pivot itself is excluded), so after at most iterations the window is a single element, which must be index by the invariant, and that element has rank .
With a three-way partition (less / equal / greater), the same argument applies with "the pivot" replaced by "the block of elements equal to the pivot", [lt, gt]: if lt <= k <= gt the answer is the pivot value. This version is essential when there are many duplicates, because Lomuto with "strictly less goes left" degrades to on an all-equal array.
Median of medians: the guarantee
Let groups, and let be the median of the group medians (the lower median if is even). At least of the group medians are (including itself). Each group whose median is contributes at least 3 elements that are — its median and the two elements above it — except possibly two groups: the group containing itself (which still contributes its median and above, but we do not need to count it carefully) and the last group, which may have fewer than 5 elements. Discarding those two groups for safety,
By the symmetric argument at least elements are . Therefore the side we recurse into, which excludes the elements on the other side of , has at most elements. (With duplicates, put elements equal to in their own middle bucket; the bound then applies to the strict sides, and if falls inside the middle bucket the answer is .)
We checked this bound empirically: across 1,500 random arrays of sizes 50 to 1,000, the smaller side never fell below 32% of the elements, comfortably above the guaranteed 30% minus the additive constant.
Complexity
Expected for randomized quickselect
Two proofs; the first gives intuition, the second is the one in CLRS.
Proof 1: phases. Call an iteration good if its pivot lands in the middle half of the current window, i.e. its rank within the window of size is between and . Then, whichever side we keep, the new window has at most elements. A uniformly random pivot is good with probability at least (half the ranks are in the middle half, up to rounding).
Group the iterations into phases: phase consists of the iterations during which the window size satisfies . A good iteration always ends the current phase. Each iteration in phase costs at most comparisons for the partition. The number of iterations in a phase is at most the number of coin flips until the first success with success probability , whose expectation is . By linearity of expectation,
The randomness is in the pivot choice, so the bound holds for every input: "expected over random pivots" is a guarantee, while "average over random inputs" is only a hope about your data.
Proof 2: recurrence. Let be the expected cost on elements, with partition cost . The pivot's rank is uniform on , and in the worst case for us we recurse on the larger side, of size :
Guess . Since (the larger half of ), the right side is at most . This is whenever , which holds for and large enough (); small are absorbed into the constant. So .
What the expectation hides. Unlike quicksort, whose running time concentrates tightly around its mean, quickselect's running time has a standard deviation proportional to . In our simulation for the median at the mean was comparisons with standard deviation , and the worst of 4,000 runs used . That spread is harmless for throughput and matters for tail latency, which is one more reason libraries add a fallback.
Worst case for median of medians
Let the non-recursive work (grouping, sorting each 5-group, partitioning) be at most . From the argument,
Recursion tree view. The two subproblems have total size about . So level 0 of the recursion tree does work, level 1 does at most , level at most . The sum of a geometric series with ratio is . Linear.
Substitution proof. Guess for all below some threshold-independent constant . Substituting,
We need , i.e. . For the fraction is at most 2, so suffices; for the algorithm runs in constant time, which we absorb by also choosing larger than for those base cases. Hence . (This is the argument of CLRS §9.3.) A small numerical check: iterating gives at , at , at and at , creeping up towards the bound of 10 and never past it.
Why groups of 3 fail and groups of 7 work
The proof needs the two recursive problem sizes to add up to a fraction strictly less than 1 of .
- Groups of 3. Half of the group medians are , and each contributes 2 elements, so only about elements are guaranteed on each side. The recurrence becomes . Now the subproblem sizes add to exactly : every level of the recursion tree does about work, and there are levels, so the argument only yields . Iterating that recurrence numerically, settles at about for from to while keeps growing (, , ). The algorithm is still correct; the standard analysis just cannot prove it linear. (Chen and Dumitrescu, "Select with groups of 3 or 4", WADS 2015, show that modified schemes with groups of 3 or 4 that repeat the median-taking step do run in linear time.)
- Groups of 5. . Linear. Five is the smallest odd group size for which the plain argument works.
- Groups of 7. At least on each side, so and . Also linear, with a smaller geometric ratio but more work to find each group median. Larger groups trade recursion depth for per-group cost; none of them is fast in practice.
Constants, comparisons and cache behaviour
The known bounds on the number of comparisons for exact median selection, as best we know them: BFPRT's paper showed at most comparisons with a refined version of their scheme; Dor and Zwick ("Selecting the median", SIAM J. Computing, 1999) improved the upper bound to about ; and the best known lower bound for deterministic algorithms is slightly above (Bent and John, 1985, proved ; Dor and Zwick later raised it to ). Randomized algorithms beat the deterministic upper bounds: Floyd–Rivest needs about in expectation, which matches the known lower bound of for randomized selection (Cunto and Munro, 1989). In our Python implementation below, Floyd–Rivest used comparisons for the median at (the term is still visible at that size), against about for random quickselect.
Memory behaviour favours quickselect: each pass is a sequential sweep over a shrinking window. The heap method reads the input once and keeps its working set in cache, which is why it wins for small . Median of medians touches the data about twice per level and naive versions allocate, which is much of why it is slow.
Implementation
Canonical: randomized quickselect with three-way partition
Iterative (no recursion, so extra space), random pivot, and a three-way partition so that arrays with many duplicates stay linear. The function copies its input so the caller's array is unchanged; drop the copy for an in-place nth_element-style routine.
import random
def kth_smallest(nums: list[int], k: int) -> int:
"""Return the element at sorted index k (0-indexed). Expected O(n)."""
if not 0 <= k < len(nums):
raise IndexError("k out of range")
a = list(nums)
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# three-way partition of a[lo..hi]: < pivot | == pivot | > pivot
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
if k < lt:
hi = lt - 1
elif k > gt:
lo = gt + 1
else:
return pivot # k falls inside the block equal to the pivot
def kth_largest(nums: list[int], k: int) -> int:
"""k-th largest, 1-indexed (LeetCode 215 convention)."""
return kth_smallest(nums, len(nums) - k)
# --- self-check (same data in all four languages) ---
assert kth_smallest([7, 2, 9, 4, 3, 8, 1, 6, 5], 4) == 5
assert kth_smallest([3, 8, 1, 9, 4, 7, 2, 6, 5], 6) == 7
assert kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert kth_smallest([2, 2, 2, 1, 1, 3], 2) == 2
assert kth_smallest([42], 0) == 42
assert kth_smallest([5, 5, 5, 5, 5, 5, 5, 5], 3) == 5
rng = random.Random(1)
for _ in range(500):
arr = [rng.randint(-50, 50) for _ in range(rng.randint(1, 60))]
k = rng.randrange(len(arr))
assert kth_smallest(arr, k) == sorted(arr)[k]
print("quickselect OK")
import java.util.Arrays;
import java.util.Random;
public class Quickselect {
static final Random RNG = new Random(7);
/** Element at sorted index k (0-indexed). Expected O(n). */
static int kthSmallest(int[] nums, int k) {
if (k < 0 || k >= nums.length) throw new IndexOutOfBoundsException("k out of range");
int[] a = nums.clone();
int lo = 0, hi = a.length - 1;
while (true) {
int pivot = a[lo + RNG.nextInt(hi - lo + 1)];
int lt = lo, i = lo, gt = hi; // < pivot | == pivot | > pivot
while (i <= gt) {
if (a[i] < pivot) swap(a, lt++, i++);
else if (a[i] > pivot) swap(a, i, gt--);
else i++;
}
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else return pivot;
}
}
static int kthLargest(int[] nums, int k) {
return kthSmallest(nums, nums.length - k);
}
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
static void check(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
public static void main(String[] args) {
check(kthSmallest(new int[]{7, 2, 9, 4, 3, 8, 1, 6, 5}, 4) == 5, "t1");
check(kthSmallest(new int[]{3, 8, 1, 9, 4, 7, 2, 6, 5}, 6) == 7, "t2");
check(kthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2) == 5, "t3");
check(kthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4, "t4");
check(kthSmallest(new int[]{2, 2, 2, 1, 1, 3}, 2) == 2, "t5");
check(kthSmallest(new int[]{42}, 0) == 42, "t6");
check(kthSmallest(new int[]{5, 5, 5, 5, 5, 5, 5, 5}, 3) == 5, "t7");
Random r = new Random(1);
for (int t = 0; t < 500; t++) {
int[] arr = new int[1 + r.nextInt(60)];
for (int i = 0; i < arr.length; i++) arr[i] = r.nextInt(101) - 50;
int k = r.nextInt(arr.length);
int[] s = arr.clone();
Arrays.sort(s);
check(kthSmallest(arr, k) == s[k], "random");
}
System.out.println("quickselect OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <stdexcept>
#include <utility>
#include <vector>
std::mt19937 rng(7);
// Element at sorted index k (0-indexed). Expected O(n).
int kthSmallest(std::vector<int> a, int k) { // by value: caller's vector untouched
if (k < 0 || k >= static_cast<int>(a.size())) throw std::out_of_range("k out of range");
int lo = 0, hi = static_cast<int>(a.size()) - 1;
while (true) {
std::uniform_int_distribution<int> pick(lo, hi);
int pivot = a[pick(rng)];
int lt = lo, i = lo, gt = hi; // < pivot | == pivot | > pivot
while (i <= gt) {
if (a[i] < pivot) std::swap(a[lt++], a[i++]);
else if (a[i] > pivot) std::swap(a[i], a[gt--]);
else ++i;
}
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else return pivot;
}
}
int kthLargest(const std::vector<int>& a, int k) {
return kthSmallest(a, static_cast<int>(a.size()) - k);
}
int main() {
assert(kthSmallest({7, 2, 9, 4, 3, 8, 1, 6, 5}, 4) == 5);
assert(kthSmallest({3, 8, 1, 9, 4, 7, 2, 6, 5}, 6) == 7);
assert(kthLargest({3, 2, 1, 5, 6, 4}, 2) == 5);
assert(kthLargest({3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4);
assert(kthSmallest({2, 2, 2, 1, 1, 3}, 2) == 2);
assert(kthSmallest({42}, 0) == 42);
assert(kthSmallest({5, 5, 5, 5, 5, 5, 5, 5}, 3) == 5);
std::mt19937 r(1);
for (int t = 0; t < 500; ++t) {
std::vector<int> arr(1 + r() % 60);
for (int& x : arr) x = static_cast<int>(r() % 101) - 50;
int k = static_cast<int>(r() % arr.size());
std::vector<int> s = arr;
std::sort(s.begin(), s.end());
assert(kthSmallest(arr, k) == s[k]);
}
std::cout << "quickselect OK\n";
}
import assert from "node:assert/strict";
/** Element at sorted index k (0-indexed). Expected O(n). */
function kthSmallest(nums: number[], k: number): number {
if (k < 0 || k >= nums.length) throw new RangeError("k out of range");
const a = nums.slice();
let lo = 0;
let hi = a.length - 1;
while (true) {
const pivot = a[lo + Math.floor(Math.random() * (hi - lo + 1))];
let lt = lo, i = lo, gt = hi; // < pivot | == pivot | > pivot
while (i <= gt) {
if (a[i] < pivot) {
[a[lt], a[i]] = [a[i], a[lt]];
lt++;
i++;
} else if (a[i] > pivot) {
[a[i], a[gt]] = [a[gt], a[i]];
gt--;
} else {
i++;
}
}
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else return pivot;
}
}
function kthLargest(nums: number[], k: number): number {
return kthSmallest(nums, nums.length - k);
}
// --- self-check ---
assert.equal(kthSmallest([7, 2, 9, 4, 3, 8, 1, 6, 5], 4), 5);
assert.equal(kthSmallest([3, 8, 1, 9, 4, 7, 2, 6, 5], 6), 7);
assert.equal(kthLargest([3, 2, 1, 5, 6, 4], 2), 5);
assert.equal(kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4);
assert.equal(kthSmallest([2, 2, 2, 1, 1, 3], 2), 2);
assert.equal(kthSmallest([42], 0), 42);
assert.equal(kthSmallest([5, 5, 5, 5, 5, 5, 5, 5], 3), 5);
for (let t = 0; t < 500; t++) {
const arr = Array.from({ length: 1 + Math.floor(Math.random() * 60) }, () => Math.floor(Math.random() * 101) - 50);
const k = Math.floor(Math.random() * arr.length);
const s = arr.slice().sort((x, y) => x - y);
assert.equal(kthSmallest(arr, k), s[k]);
}
console.log("quickselect OK");
The pivot is a value read before partitioning, so the loop never tracks where the pivot moved, and the three-way test handles duplicates for free: eight 5s finish in one pass because lt = 0 and gt = 7 bracket every k.
Deterministic: median of medians
This version allocates new lists at each level, which keeps the algorithm visible. It is the textbook algorithm, with the three-way split that makes the bound hold even with duplicates.
def mom_select(a: list[int], k: int) -> int:
"""k-th smallest (0-indexed) in worst-case O(n): Blum-Floyd-Pratt-Rivest-Tarjan."""
if len(a) <= 5:
return sorted(a)[k]
# 1-2. medians of groups of five (last group may be shorter)
medians = [sorted(a[i:i + 5])[(len(a[i:i + 5]) - 1) // 2] for i in range(0, len(a), 5)]
# 3. pivot = median of the medians, found recursively
pivot = mom_select(medians, (len(medians) - 1) // 2)
# 4. three-way split around the pivot
lows = [x for x in a if x < pivot]
highs = [x for x in a if x > pivot]
n_equal = len(a) - len(lows) - len(highs)
# 5. recurse into the one side that holds rank k
if k < len(lows):
return mom_select(lows, k)
if k < len(lows) + n_equal:
return pivot
return mom_select(highs, k - len(lows) - n_equal)
# --- self-check ---
import random
data = [42, 20, 51, 84, 7, 10, 69, 13, 47, 75, 8, 65, 28, 5, 12,
56, 54, 9, 31, 85, 71, 55, 89, 73, 16]
assert mom_select(data, 12) == 47
assert mom_select([7, 2, 9, 4, 3, 8, 1, 6, 5], 4) == 5
assert mom_select([2, 2, 2, 1, 1, 3], 2) == 2
assert mom_select(list(range(1000, 0, -1)), 0) == 1
rng = random.Random(2)
for _ in range(300):
arr = [rng.randint(0, 40) for _ in range(rng.randint(1, 200))]
k = rng.randrange(len(arr))
assert mom_select(arr, k) == sorted(arr)[k]
print("median of medians OK")
import java.util.Arrays;
import java.util.Random;
public class MedianOfMedians {
/** k-th smallest (0-indexed) in worst-case O(n). */
static int momSelect(int[] a, int k) {
if (a.length <= 5) {
int[] s = a.clone();
Arrays.sort(s);
return s[k];
}
int groups = (a.length + 4) / 5;
int[] medians = new int[groups];
for (int g = 0; g < groups; g++) {
int[] grp = Arrays.copyOfRange(a, 5 * g, Math.min(5 * g + 5, a.length));
Arrays.sort(grp);
medians[g] = grp[(grp.length - 1) / 2];
}
int pivot = momSelect(medians, (groups - 1) / 2);
int nLow = 0, nHigh = 0;
for (int x : a) { if (x < pivot) nLow++; else if (x > pivot) nHigh++; }
int[] lows = new int[nLow], highs = new int[nHigh];
int li = 0, hi = 0;
for (int x : a) { if (x < pivot) lows[li++] = x; else if (x > pivot) highs[hi++] = x; }
int nEqual = a.length - nLow - nHigh;
if (k < nLow) return momSelect(lows, k);
if (k < nLow + nEqual) return pivot;
return momSelect(highs, k - nLow - nEqual);
}
static void check(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
public static void main(String[] args) {
int[] data = {42, 20, 51, 84, 7, 10, 69, 13, 47, 75, 8, 65, 28, 5, 12,
56, 54, 9, 31, 85, 71, 55, 89, 73, 16};
check(momSelect(data, 12) == 47, "t1");
check(momSelect(new int[]{7, 2, 9, 4, 3, 8, 1, 6, 5}, 4) == 5, "t2");
check(momSelect(new int[]{2, 2, 2, 1, 1, 3}, 2) == 2, "t3");
int[] desc = new int[1000];
for (int i = 0; i < 1000; i++) desc[i] = 1000 - i;
check(momSelect(desc, 0) == 1, "t4");
Random r = new Random(2);
for (int t = 0; t < 300; t++) {
int[] arr = new int[1 + r.nextInt(200)];
for (int i = 0; i < arr.length; i++) arr[i] = r.nextInt(41);
int k = r.nextInt(arr.length);
int[] s = arr.clone();
Arrays.sort(s);
check(momSelect(arr, k) == s[k], "random");
}
System.out.println("median of medians OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
// k-th smallest (0-indexed) in worst-case O(n).
int momSelect(const std::vector<int>& a, int k) {
if (a.size() <= 5) {
std::vector<int> s = a;
std::sort(s.begin(), s.end());
return s[k];
}
std::vector<int> medians;
for (std::size_t i = 0; i < a.size(); i += 5) {
std::vector<int> grp(a.begin() + i, a.begin() + std::min(i + 5, a.size()));
std::sort(grp.begin(), grp.end());
medians.push_back(grp[(grp.size() - 1) / 2]);
}
int pivot = momSelect(medians, static_cast<int>((medians.size() - 1) / 2));
std::vector<int> lows, highs;
for (int x : a) {
if (x < pivot) lows.push_back(x);
else if (x > pivot) highs.push_back(x);
}
int nLow = static_cast<int>(lows.size());
int nEqual = static_cast<int>(a.size()) - nLow - static_cast<int>(highs.size());
if (k < nLow) return momSelect(lows, k);
if (k < nLow + nEqual) return pivot;
return momSelect(highs, k - nLow - nEqual);
}
int main() {
std::vector<int> data = {42, 20, 51, 84, 7, 10, 69, 13, 47, 75, 8, 65, 28, 5, 12,
56, 54, 9, 31, 85, 71, 55, 89, 73, 16};
assert(momSelect(data, 12) == 47);
assert(momSelect({7, 2, 9, 4, 3, 8, 1, 6, 5}, 4) == 5);
assert(momSelect({2, 2, 2, 1, 1, 3}, 2) == 2);
std::vector<int> desc(1000);
for (int i = 0; i < 1000; ++i) desc[i] = 1000 - i;
assert(momSelect(desc, 0) == 1);
std::mt19937 r(2);
for (int t = 0; t < 300; ++t) {
std::vector<int> arr(1 + r() % 200);
for (int& x : arr) x = static_cast<int>(r() % 41);
int k = static_cast<int>(r() % arr.size());
std::vector<int> s = arr;
std::sort(s.begin(), s.end());
assert(momSelect(arr, k) == s[k]);
}
std::cout << "median of medians OK\n";
}
import assert from "node:assert/strict";
/** k-th smallest (0-indexed) in worst-case O(n). */
function momSelect(a: number[], k: number): number {
if (a.length <= 5) return a.slice().sort((x, y) => x - y)[k];
const medians: number[] = [];
for (let i = 0; i < a.length; i += 5) {
const grp = a.slice(i, i + 5).sort((x, y) => x - y);
medians.push(grp[(grp.length - 1) >> 1]);
}
const pivot = momSelect(medians, (medians.length - 1) >> 1);
const lows = a.filter((x) => x < pivot);
const highs = a.filter((x) => x > pivot);
const nEqual = a.length - lows.length - highs.length;
if (k < lows.length) return momSelect(lows, k);
if (k < lows.length + nEqual) return pivot;
return momSelect(highs, k - lows.length - nEqual);
}
// --- self-check ---
const data = [42, 20, 51, 84, 7, 10, 69, 13, 47, 75, 8, 65, 28, 5, 12,
56, 54, 9, 31, 85, 71, 55, 89, 73, 16];
assert.equal(momSelect(data, 12), 47);
assert.equal(momSelect([7, 2, 9, 4, 3, 8, 1, 6, 5], 4), 5);
assert.equal(momSelect([2, 2, 2, 1, 1, 3], 2), 2);
assert.equal(momSelect(Array.from({ length: 1000 }, (_, i) => 1000 - i), 0), 1);
for (let t = 0; t < 300; t++) {
const arr = Array.from({ length: 1 + Math.floor(Math.random() * 200) }, () => Math.floor(Math.random() * 41));
const k = Math.floor(Math.random() * arr.length);
assert.equal(momSelect(arr, k), arr.slice().sort((x, y) => x - y)[k]);
}
console.log("median of medians OK");
An in-place version moves the group medians to the front of the window and recurses on that prefix (CLRS §9.3).
Top- with a bounded heap
Return the largest values in descending order. Python's heapq, Java's PriorityQueue and C++'s std::priority_queue provide the heap; TypeScript has no built-in heap, so we write a minimal one.
import heapq
def top_k(nums: list[int], k: int) -> list[int]:
"""The k largest values, largest first. O(n log k) time, O(k) space, one pass."""
if k <= 0:
return []
heap: list[int] = [] # min-heap of the k largest seen so far
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # pop root and push x in one sift
return sorted(heap, reverse=True)
# --- self-check ---
assert top_k([3, 2, 1, 5, 6, 4], 2) == [6, 5]
assert top_k([7, 2, 9, 4, 3, 8, 1, 6, 5], 3) == [9, 8, 7]
assert top_k([1, 1, 1, 2, 2, 3], 2) == [3, 2]
assert top_k([4], 3) == [4]
assert top_k([5, 1], 0) == []
print("top_k OK")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class TopK {
/** The k largest values, largest first. O(n log k). */
static List<Integer> topK(int[] nums, int k) {
List<Integer> out = new ArrayList<>();
if (k <= 0) return out;
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
for (int x : nums) {
if (heap.size() < k) heap.add(x);
else if (x > heap.peek()) { heap.poll(); heap.add(x); }
}
out.addAll(heap);
out.sort(Collections.reverseOrder());
return out;
}
static void check(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
public static void main(String[] args) {
check(topK(new int[]{3, 2, 1, 5, 6, 4}, 2).equals(List.of(6, 5)), "t1");
check(topK(new int[]{7, 2, 9, 4, 3, 8, 1, 6, 5}, 3).equals(List.of(9, 8, 7)), "t2");
check(topK(new int[]{1, 1, 1, 2, 2, 3}, 2).equals(List.of(3, 2)), "t3");
check(topK(new int[]{4}, 3).equals(List.of(4)), "t4");
check(topK(new int[]{5, 1}, 0).isEmpty(), "t5");
System.out.println("topK OK");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
// The k largest values, largest first. O(n log k).
std::vector<int> topK(const std::vector<int>& nums, int k) {
if (k <= 0) return {};
std::priority_queue<int, std::vector<int>, std::greater<int>> heap; // min-heap
for (int x : nums) {
if (static_cast<int>(heap.size()) < k) heap.push(x);
else if (x > heap.top()) { heap.pop(); heap.push(x); }
}
std::vector<int> out;
while (!heap.empty()) { out.push_back(heap.top()); heap.pop(); }
std::reverse(out.begin(), out.end());
return out;
}
int main() {
assert((topK({3, 2, 1, 5, 6, 4}, 2) == std::vector<int>{6, 5}));
assert((topK({7, 2, 9, 4, 3, 8, 1, 6, 5}, 3) == std::vector<int>{9, 8, 7}));
assert((topK({1, 1, 1, 2, 2, 3}, 2) == std::vector<int>{3, 2}));
assert((topK({4}, 3) == std::vector<int>{4}));
assert(topK({5, 1}, 0).empty());
std::cout << "topK OK\n";
}
import assert from "node:assert/strict";
class MinHeap {
private a: number[] = [];
get size(): number { return this.a.length; }
peek(): number { return this.a[0]; }
push(x: number): void {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] <= a[i]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
replaceTop(x: number): void { // pop root, push x, one sift-down
const a = this.a;
a[0] = x;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l] < a[m]) m = l;
if (r < a.length && a[r] < a[m]) m = r;
if (m === i) return;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
toArray(): number[] { return this.a.slice(); }
}
/** The k largest values, largest first. O(n log k). */
function topK(nums: number[], k: number): number[] {
if (k <= 0) return [];
const heap = new MinHeap();
for (const x of nums) {
if (heap.size < k) heap.push(x);
else if (x > heap.peek()) heap.replaceTop(x);
}
return heap.toArray().sort((x, y) => y - x);
}
// --- self-check ---
assert.deepEqual(topK([3, 2, 1, 5, 6, 4], 2), [6, 5]);
assert.deepEqual(topK([7, 2, 9, 4, 3, 8, 1, 6, 5], 3), [9, 8, 7]);
assert.deepEqual(topK([1, 1, 1, 2, 2, 3], 2), [3, 2]);
assert.deepEqual(topK([4], 3), [4]);
assert.deepEqual(topK([5, 1], 0), []);
console.log("topK OK");
Trace of the bounded heap on [3, 2, 1, 5, 6, 4] with k = 2 (the root is the current answer):
| Read | Heap before | Action | Heap after | Root (2nd largest so far) |
|---|---|---|---|---|
| 3 | [] | size < 2: push | [3] | — |
| 2 | [3] | size < 2: push | [2, 3] | 2 |
| 1 | [2, 3] | 1 ≤ root 2: skip | [2, 3] | 2 |
| 5 | [2, 3] | 5 > 2: replace root | [3, 5] | 3 |
| 6 | [3, 5] | 6 > 3: replace root | [5, 6] | 5 |
| 4 | [5, 6] | 4 ≤ root 5: skip | [5, 6] | 5 |
Variant: introselect
Musser's idea in a dozen lines: run quickselect with a cheap pivot (median of three here), give it a budget of partition rounds, and if the budget runs out, finish with median of medians. Any input that defeats median-of-three costs at most before the switch and then , and in practice the budget is never exhausted on non-adversarial data.
import random
def mom_select(a: list[int], k: int) -> int:
if len(a) <= 5:
return sorted(a)[k]
meds = [sorted(a[i:i + 5])[(len(a[i:i + 5]) - 1) // 2] for i in range(0, len(a), 5)]
p = mom_select(meds, (len(meds) - 1) // 2)
lows = [x for x in a if x < p]
highs = [x for x in a if x > p]
eq = len(a) - len(lows) - len(highs)
if k < len(lows):
return mom_select(lows, k)
if k < len(lows) + eq:
return p
return mom_select(highs, k - len(lows) - eq)
def introselect(nums: list[int], k: int) -> int:
a = list(nums)
lo, hi = 0, len(a) - 1
budget = 2 * max(1, len(a).bit_length() - 1) # 2 * floor(log2 n)
while hi > lo:
if budget == 0: # too many bad pivots
return mom_select(a[lo:hi + 1], k - lo)
budget -= 1
mid = (lo + hi) // 2
pivot = sorted((a[lo], a[mid], a[hi]))[1] # median of three
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]; gt -= 1
else:
i += 1
if k < lt:
hi = lt - 1
elif k > gt:
lo = gt + 1
else:
return pivot
return a[lo]
rng = random.Random(5)
for _ in range(500):
arr = [rng.randint(0, 100) for _ in range(rng.randint(1, 300))]
k = rng.randrange(len(arr))
assert introselect(arr, k) == sorted(arr)[k]
assert introselect(list(range(5000)), 2500) == 2500 # sorted input
assert introselect([1] * 1000, 999) == 1 # all equal
print("introselect OK")
The C++ standard library exposes exactly this contract. std::nth_element(first, nth, last) rearranges the range so that *nth is the element that would be there after sorting, everything before it is not greater, and everything after is not less. The standard requires linear time on average. libstdc++ implements it as introselect whose fallback is a heap-based selection, so its worst case is rather than .
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {3, 8, 1, 9, 4, 7, 2, 6, 5};
std::nth_element(v.begin(), v.begin() + 6, v.end());
assert(v[6] == 7);
for (int i = 0; i < 6; ++i) assert(v[i] <= v[6]);
for (int i = 7; i < 9; ++i) assert(v[i] >= v[6]);
// top-3 largest: partition so the 3 largest sit at the end, then sort just those
std::vector<int> w = {7, 2, 9, 4, 3, 8, 1, 6, 5};
std::nth_element(w.begin(), w.end() - 3, w.end());
std::sort(w.end() - 3, w.end());
assert((std::vector<int>(w.end() - 3, w.end()) == std::vector<int>{7, 8, 9}));
// std::partial_sort: the k smallest, in order, O(n log k) via a heap
std::vector<int> z = {7, 2, 9, 4, 3, 8, 1, 6, 5};
std::partial_sort(z.begin(), z.begin() + 3, z.end());
assert(z[0] == 1 && z[1] == 2 && z[2] == 3);
std::cout << "nth_element OK\n";
}
Variant: Floyd–Rivest
Floyd and Rivest's SELECT ("Expected time bounds for selection" and "Algorithm 489", both CACM 18(3), 1975) samples about elements, recursively selects two elements from the sample that should bracket rank , and partitions the window around them. With high probability the true -th element lies between the two and only a small window survives. The version below follows the published algorithm's structure; it recurses on the sample only when the window is larger than 600 elements.
import math
import random
def floyd_rivest(a: list[int], left: int, right: int, k: int) -> int:
"""In place: after the call a[k] is the k-th smallest of a[left..right]."""
while right > left:
if right - left > 600:
# recurse on a sample to move a[k] close to its final value
n = right - left + 1
i = k - left + 1
z = math.log(n)
s = 0.5 * math.exp(2 * z / 3)
sd = 0.5 * math.sqrt(z * s * (n - s) / n) * (1 if i - n / 2 >= 0 else -1)
new_left = max(left, int(k - i * s / n + sd))
new_right = min(right, int(k + (n - i) * s / n + sd))
floyd_rivest(a, new_left, new_right, k)
t = a[k]
i, j = left, right
a[left], a[k] = a[k], a[left]
if a[right] > t:
a[right], a[left] = a[left], a[right]
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
while a[i] < t:
i += 1
while a[j] > t:
j -= 1
if a[left] == t:
a[left], a[j] = a[j], a[left]
else:
j += 1
a[j], a[right] = a[right], a[j]
if j <= k:
left = j + 1
if k <= j:
right = j - 1
return a[k]
rng = random.Random(3)
for _ in range(200):
n = rng.randint(1, 3000)
arr = [rng.randint(0, rng.choice([5, 1000, 10**6])) for _ in range(n)]
k = rng.randrange(n)
assert floyd_rivest(arr[:], 0, n - 1, k) == sorted(arr)[k]
print("floyd-rivest OK")
Use it when comparisons are expensive (long strings, composite keys) and is large.
Variant: weighted median
Each value carries a positive weight with total . The (lower) weighted median is the value such that the weights strictly below it sum to less than and the weights strictly above it sum to at most . It minimises : moving to the right by increases the distance to every point on the left (total weight ) and decreases it to every point on the right (total weight ), changing the cost by , so the cost decreases while and the optimum is where the cumulative weight crosses .
Example (computed by script): values 1, 3, 4, 7, 10 with weights 2, 7, 1, 4, 6, total .
| Value | Weight | Cumulative weight | Cost if = this value |
|---|---|---|---|
| 1 | 2 | 2 | 95 |
| 3 | 7 | 9 | 63 |
| 4 | 1 | 10 | 61 |
| 7 | 4 | 14 | 61 |
| 10 | 6 | 20 | 85 |
The cumulative weight first reaches at value 4, the lower weighted median. Because it reaches exactly half, every point in is optimal (cost 61), just as any point between the two middle elements minimises the unweighted sum of distances for even . Sorting gives an algorithm; the selection version below is expected : partition around a random pivot, add up the weight on the left, and recurse only into the side that contains the half-weight point (CLRS Problem 9-2).
import random
def weighted_median_sort(pairs: list[tuple[int, int]]) -> int:
total = sum(w for _, w in pairs)
acc = 0
for v, w in sorted(pairs):
acc += w
if 2 * acc >= total:
return v
raise ValueError("empty input")
def weighted_median(pairs: list[tuple[int, int]]) -> int:
"""Lower weighted median in expected O(n): quickselect on cumulative weight."""
total = sum(w for _, w in pairs)
items = list(pairs)
below = 0 # weight known to lie strictly left of `items`
while True:
pv = random.choice(items)[0]
lows = [p for p in items if p[0] < pv]
eq_w = sum(w for v, w in items if v == pv)
low_w = sum(w for _, w in lows)
if 2 * (below + low_w) >= total: # half-weight point is strictly left
items = lows
elif 2 * (below + low_w + eq_w) >= total: # it lands on the pivot value
return pv
else:
below += low_w + eq_w
items = [p for p in items if p[0] > pv]
def cost(pairs: list[tuple[int, int]], x: int) -> int:
return sum(w * abs(v - x) for v, w in pairs)
ex = [(1, 2), (3, 7), (4, 1), (7, 4), (10, 6)]
assert weighted_median_sort(ex) == 4 and weighted_median(ex) == 4
assert [cost(ex, x) for x in (1, 3, 4, 7, 10)] == [95, 63, 61, 61, 85]
rng = random.Random(9)
for _ in range(300):
ps = [(rng.randint(-20, 20), rng.randint(1, 9)) for _ in range(rng.randint(1, 40))]
m = weighted_median(ps)
assert m == weighted_median_sort(ps)
assert cost(ps, m) == min(cost(ps, x) for x in range(-21, 22))
print("weighted median OK")
Variant: order statistics on a changing set
When elements are inserted and deleted between queries, re-running quickselect costs per query. An order-statistic tree is a balanced BST (red-black, AVL, treap) in which every node also stores the size of its subtree. Then:
select(k): at a node with left subtree size , if go left; if this node is the answer; otherwise go right with .rank(x): walk down from the root, adding whenever you go right.
Rotations update sizes in (a node's size is its children's sizes), so both queries and updates stay . The balancing machinery itself is the subject of Balanced BSTs: AVL & Red-Black Trees (CLRS §14.1 gives the augmentation in full); Treaps, Splay Trees & Skip Lists shows the same size augmentation on a treap, which is the easiest to code in a contest. In C++, GNU's policy-based tree with tree_order_statistics_node_update provides find_by_order and order_of_key out of the box (GCC only).
When values are integers from a bounded range (or can be coordinate-compressed to one), a Fenwick tree over counts does the same job in a few lines: rank(x) is a prefix sum, and select(k) is a binary-lifting descent through the tree.
class OrderStatisticBIT:
"""Multiset of integers in [0, size). insert/remove/rank/select in O(log size)."""
def __init__(self, size: int) -> None:
self.n = size
self.tree = [0] * (size + 1)
self.count = 0
self.log = size.bit_length()
def add(self, x: int, delta: int) -> None:
self.count += delta
i = x + 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def rank(self, x: int) -> int:
"""Number of stored elements strictly less than x."""
s, i = 0, x
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def select(self, k: int) -> int:
"""k-th smallest stored element (0-indexed), by binary lifting."""
pos = 0
for b in range(self.log, -1, -1):
nxt = pos + (1 << b)
if nxt <= self.n and self.tree[nxt] <= k:
pos = nxt
k -= self.tree[nxt]
return pos # 1-based position pos+1 holds it, i.e. value pos
ost = OrderStatisticBIT(100)
for v in [42, 7, 19, 7, 88, 63]:
ost.add(v, +1)
assert [ost.select(i) for i in range(6)] == [7, 7, 19, 42, 63, 88]
assert ost.rank(42) == 3 and ost.rank(7) == 0 and ost.rank(100) == 6
ost.add(7, -1)
assert ost.select(1) == 19 and ost.count == 5
print("order-statistic BIT OK")
Real systems use the same augmentation: Redis sorted sets are skip lists in which every forward pointer records its span (how many elements it skips), so ZRANK and ZRANGE ... BY INDEX are (Redis Internals).
Variant: top- over a stream in
The bounded heap costs per element in the worst case (for example, an increasing stream, where every element replaces the root). A buffer trick removes the log: keep an array of capacity . Append each incoming element (after rejecting it if it is not larger than the current threshold). When the buffer is full, run quickselect to keep only its largest, and record the smallest of those as the new threshold. Each compaction costs and happens at most once per insertions, so the amortised cost is per element and overall including the final sort. Google's Guava library uses this scheme in Ordering.leastOf / TopKSelector.
import random
def kth_smallest(a: list[int], k: int) -> int:
lo, hi = 0, len(a) - 1
a = list(a)
while True:
p = a[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < p:
a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
elif a[i] > p:
a[i], a[gt] = a[gt], a[i]; gt -= 1
else:
i += 1
if k < lt:
hi = lt - 1
elif k > gt:
lo = gt + 1
else:
return p
def stream_top_k(stream, k: int) -> list[int]:
"""k largest of an iterable in amortised O(1) per element, O(k) memory."""
buf: list[int] = []
threshold = None
for x in stream:
if threshold is not None and x <= threshold and len(buf) >= k:
continue # cannot be in the top k
buf.append(x)
if len(buf) >= 2 * k:
cut = kth_smallest(buf, len(buf) - k) # value of the k-th largest
greater = [y for y in buf if y > cut]
buf = greater + [cut] * (k - len(greater))
threshold = cut
return sorted(buf, reverse=True)[:k]
rng = random.Random(4)
for _ in range(100):
data = [rng.randint(0, 1000) for _ in range(rng.randint(1, 2000))]
k = rng.randint(1, 50)
assert stream_top_k(iter(data), k) == sorted(data, reverse=True)[:k]
assert stream_top_k(range(10000), 3) == [9999, 9998, 9997] # increasing stream
print("stream top-k OK")
Real-world uses
- Percentiles in monitoring. p50/p95/p99 latency is an order statistic. Exact computation over a window of samples is quickselect (or a sort, if you want many percentiles at once). At scale, systems use quantile sketches instead: Elasticsearch's
percentilesaggregation uses t-digest (Dunning), Apache DataSketches implements the KLL sketch (Karnin, Lang and Liberty, 2016), and Prometheus estimates quantiles from histogram buckets withhistogram_quantile. They all trade exactness for kilobytes of memory and mergeability across machines. Greenwald and Khanna (SIGMOD 2001) gave the classic deterministic -approximate quantile summary. ORDER BY … LIMIT kin databases. PostgreSQL's executor recognises a bounded sort and keeps a heap of tuples;EXPLAIN ANALYZEreports it asSort Method: top-N heapsort, with memory proportional to instead of the table size. See Query Planning & Optimization. Ordered-set aggregates such aspercentile_discandpercentile_contsort their group, so they cost per group.- Numerical libraries. NumPy's
np.partitionandnp.argpartitiondefault tokind="introselect", andnp.medianandnp.percentileare built on partitioning rather than full sorts. C++ hasstd::nth_elementandstd::partial_sort; Rust hasslice::select_nth_unstable, whose documentation states a linear worst case via a median-of-medians fallback. Python'sheapq.nlargest/nsmallestuse the bounded-heap method (with shortcuts tomax/minwhen and tosortedwhen ). Java's standard library has no selection routine; aPriorityQueueof size is the idiomatic substitute. - Spatial indexes. Building a balanced k-d tree splits the points at the median coordinate at each level; with linear-time selection the whole build is (Spatial Trees, Spatial Indexing).
- Robust statistics and signal processing. Median filters remove salt-and-pepper noise from images by replacing each pixel with the median of its neighbourhood; sliding-window medians smooth sensor data without being dragged by outliers.
- Search and recommendation. Ranking pipelines score thousands to millions of candidates and keep the top few hundred for a more expensive re-ranker: bounded heaps per shard, then a merge of the per-shard top- lists (Search Engineering). Merging per-shard top- lists is correct because any global top- item is in its own shard's top .
Pitfalls & edge cases
- Off-by-one between "k-th largest" and index. LeetCode's "-th largest" is 1-indexed from the top; the sorted index is . Write the conversion once, in a wrapper, and test and .
- Fixed pivots on sorted input. "Last element" or "first element" as pivot is on sorted or reverse-sorted data, which is the most common real-world input after random. Randomise, or use median-of-three plus a fallback.
- Two-way partition with many duplicates. Lomuto with "strictly less goes left" puts all equal elements on one side; on an all-equal array every partition removes one element and the run is quadratic. Use a three-way partition or Hoare's scheme (which stops on equal elements from both sides).
- Recursion into both sides. A surprisingly common bug when adapting quicksort code: forgetting to return after recursing, or recursing into both halves, silently turns quickselect back into quicksort. It is still correct, so tests pass; only the running time betrays it.
- Re-indexing confusion. Mixing "absolute " with "relative inside the window" gives wrong answers only on some inputs. Pick one convention. The iterative version with absolute and shrinking
[lo, hi]is the least error-prone. - Mutating the caller's array. In-place quickselect reorders the input; copy, or document it.
- Heap direction. For the largest you need a min-heap of size (so the root is the weakest member and is the one to evict). Using a max-heap of size keeps the smallest instead. Python's
heapqis a min-heap; negate keys for a max-heap. Java'sPriorityQueueis a min-heap by default; C++'spriority_queueis a max-heap by default, so you needstd::greater<>. - Ties in top-. "Top frequent" can have ties at the boundary; decide whether you return exactly items (and which ones) or all items tied with the -th. Interviewers often care that you ask.
- Even-length medians. "The median" of an even-length array may mean the lower middle, the upper middle, or their average. The average of two integers can overflow in fixed-width languages and is not an integer; compute
lo + (hi - lo) / 2in floating point or as a fraction. - Median of medians off-by-ones. The last group may have fewer than 5 elements; the median of the medians must be the lower median when the count is even; and elements equal to the pivot must not all go to one side. Test with and with heavy duplicates.
- NaN and incomparable keys. Floating-point NaN compares false with everything, which breaks partition invariants (and the
std::nth_elementprecondition of a strict weak ordering). Filter NaNs first. - Assuming "expected linear" means "always fast". The running time has standard deviation , and a predictable seed or fixed pivot rule can be attacked with crafted inputs.
Variations
- Partial sort / top- in order. Select, then sort the survivors: .
std::partial_sortuses a heap instead: . - Multiselect. Finding several order statistics at once (all deciles, say) by recursing into every side that contains a wanted rank: for ranks. NumPy's
np.partitionaccepts a sequence ofkthvalues for this reason. - Selection in two sorted arrays. The -th smallest of the union of two sorted arrays of sizes and takes by binary searching how many elements come from the first array. This is the heart of Median of Two Sorted Arrays.
- Selection in a sorted matrix or implicit set. When the candidates are pairwise sums, distances or fractions ( of them), binary search on the answer value and count how many candidates are with two pointers. Frederickson and Johnson gave an algorithm for selection in an sorted matrix; the binary-search version is and is what you write in an interview.
- Running median. Two heaps (a max-heap for the lower half, a min-heap for the upper half, rebalanced so sizes differ by at most one) give insert and median (Heaps & Priority Queues). A sliding window also needs deletion: lazy deletion in the heaps, or an order-statistic structure.
- Approximate selection. Sample elements and select within the sample: the rank error is about . Quantile sketches make this rigorous and mergeable.
- Order statistics in other structures. Subtree-size augmentation works on any balanced tree; position-indexed implicit treaps use it to support "insert at index " in ; wavelet trees answer "-th smallest in a subarray " in ; persistent segment trees answer the same offline.
Practice ladder
Thirteen problems, easiest first. Descriptions are in our own words; follow the link for the official statement.
1. Kth Largest Element in a Stream (LeetCode 703) — Maintain the -th largest value of a growing multiset as numbers arrive one by one. Teaches the bounded min-heap in its purest form.
Hint
Keep a min-heap of at most elements; after each insertion, pop while the size exceeds . The root is the answer.
2. Kth Largest Element in an Array (LeetCode 215) — Return the -th largest value of an unsorted array, ideally without sorting. Teaches quickselect and the "" index conversion; the test data includes adversarial cases for naive pivots.
Hint
Random pivot and three-way partition. The judge has inputs with long runs of equal values, which kill a two-way Lomuto partition.
Solution
import random
def find_kth_largest(nums: list[int], k: int) -> int:
a, target = list(nums), len(nums) - k
lo, hi = 0, len(a) - 1
while True:
p = a[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < p:
a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
elif a[i] > p:
a[i], a[gt] = a[gt], a[i]; gt -= 1
else:
i += 1
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return p
assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert find_kth_largest([1] * 10000, 5000) == 1
print("ok")
Expected time, for the copy (or if you partition in place).
3. Kth Smallest Element in a BST (LeetCode 230) — Find the -th smallest key in a binary search tree. Teaches that an in-order traversal enumerates order statistics, and sets up the follow-up "what if the tree is modified often?" whose answer is subtree-size augmentation.
Hint
Iterative in-order traversal with a stack, stop after pops: . For frequent updates, store subtree sizes and descend in .
4. K Closest Points to Origin (LeetCode 973) — Return any points nearest to . Teaches selection with a computed key, and that the output order does not matter so you need no final sort.
Hint
Compare squared distances (no square roots, no floating point). Either a max-heap of size keyed by distance, or quickselect on the distance array.
Solution
import random
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
pts = list(points)
d = lambda p: p[0] * p[0] + p[1] * p[1]
lo, hi = 0, len(pts) - 1
while lo < hi:
pv = d(pts[random.randint(lo, hi)])
lt, i, gt = lo, lo, hi
while i <= gt:
if d(pts[i]) < pv:
pts[lt], pts[i] = pts[i], pts[lt]; lt += 1; i += 1
elif d(pts[i]) > pv:
pts[i], pts[gt] = pts[gt], pts[i]; gt -= 1
else:
i += 1
if k - 1 < lt:
hi = lt - 1
elif k - 1 > gt:
lo = gt + 1
else:
break
return pts[:k]
res = k_closest([[3, 3], [5, -1], [-2, 4]], 2)
assert sorted(res) == [[-2, 4], [3, 3]]
assert k_closest([[1, 3], [-2, 2]], 1) == [[-2, 2]]
print("ok")
After the loop, index holds the -th closest point and everything before it is no farther, so pts[:k] is a valid answer. Expected .
5. Top K Frequent Elements (LeetCode 347) — Return the values that occur most often. Teaches combining a hash-map count with selection, and the bucket-by-frequency trick that is linear without any randomness.
Hint
Frequencies are integers in . Bucket values by their count, then walk buckets from down until you have values.
Solution
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
count = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for value, c in count.items():
buckets[c].append(value)
out: list[int] = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
out.append(value)
if len(out) == k:
return out
return out
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
print("ok")
time and space, deterministic. The heap version is ; quickselect over the distinct values is expected .
6. Kth Smallest Element in a Sorted Matrix (LeetCode 378) — Rows and columns are each sorted; find the -th smallest entry overall. Teaches two approaches: a heap that merges sorted rows, and binary search on the value with a staircase count.
Hint
Count entries by walking from the bottom-left corner: move right when the entry is (adding the column height), up otherwise. Binary search the smallest with count .
7. Find Median from Data Stream (LeetCode 295) — Support "add a number" and "report the current median". Teaches the two-heap running median.
Hint
Max-heap for the lower half, min-heap for the upper half. After each insert, move one element across if the sizes differ by more than one or if the tops are out of order.
8. Stick Lengths (CSES 1074) — Change every stick to a common length at a cost equal to the total absolute change; minimise the cost. Teaches that the median minimises the sum of absolute deviations.
Hint
The optimal common length is any median. Sum , using 64-bit integers.
Solution
def stick_lengths(xs: list[int]) -> int:
s = sorted(xs) # or quickselect for the median in O(n)
m = s[len(s) // 2]
return sum(abs(x - m) for x in s)
assert stick_lengths([2, 3, 1, 5, 2]) == 5
assert stick_lengths([7]) == 0
assert stick_lengths([1, 10]) == 9
print("ok")
with the sort; expected with quickselect. The cost function is convex and piecewise linear with slope , which is zero at the median.
9. Sliding Window Median (CSES 1076) — Report the median of every window of consecutive elements. Teaches dynamic order statistics: insert one, delete one, query the middle.
Hint
Two heaps with lazy deletion, or two balanced multisets (std::multiset in C++), or a Fenwick tree over compressed values with select.
10. Sliding Window Cost (CSES 1077) — For each window, the minimum total cost to make all its elements equal. Teaches maintaining sums on both sides of the running median.
Hint
Keep the lower and upper halves with their sums; the cost is median * |low| - sum(low) + sum(high) - median * |high|.
11. Wiggle Sort II (LeetCode 324) — Reorder so that a[0] < a[1] > a[2] < a[3] … strictly. Teaches using the median as a separator, plus a three-way partition through a virtual index mapping to reach time and space.
Hint
Find the median with quickselect. Then three-way partition around it, but address index as (1 + 2*i) % (n | 1) so that larger elements land on odd positions and smaller ones on even positions, keeping equal-to-median values apart.
12. Find K-th Smallest Pair Distance (LeetCode 719) — Among all pairwise absolute differences, return the -th smallest. Teaches selection over an implicit set via binary search on the answer.
Hint
Sort. For a candidate distance , count pairs with difference using a sliding window in . Binary search the smallest whose count is .
Solution
def smallest_distance_pair(nums: list[int], k: int) -> int:
a = sorted(nums)
def pairs_at_most(d: int) -> int:
count = left = 0
for right, x in enumerate(a):
while x - a[left] > d:
left += 1
count += right - left
return count
lo, hi = 0, a[-1] - a[0]
while lo < hi:
mid = (lo + hi) // 2
if pairs_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
assert smallest_distance_pair([1, 3, 1], 1) == 0
assert smallest_distance_pair([1, 1, 1], 2) == 0
assert smallest_distance_pair([1, 6, 1], 3) == 5
print("ok")
where is the value range. The answer is always an actual pair distance because the count function only changes value at pair distances.
13. Median of Two Sorted Arrays (LeetCode 4) — The median of the union of two sorted arrays in . Teaches selection by binary searching a partition point.
Hint
Binary search = how many elements the smaller array contributes to the left half; follows. The partition is right when A[i-1] <= B[j] and B[j-1] <= A[i].
Solution
def find_median_sorted_arrays(a: list[int], b: list[int]) -> float:
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
half = (m + n + 1) // 2
lo, hi = 0, m
inf = float("inf")
while lo <= hi:
i = (lo + hi) // 2
j = half - i
a_left = a[i - 1] if i > 0 else -inf
a_right = a[i] if i < m else inf
b_left = b[j - 1] if j > 0 else -inf
b_right = b[j] if j < n else inf
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2:
return float(max(a_left, b_left))
return (max(a_left, b_left) + min(a_right, b_right)) / 2
if a_left > b_right:
hi = i - 1
else:
lo = i + 1
raise ValueError("inputs not sorted")
assert find_median_sorted_arrays([1, 3], [2]) == 2.0
assert find_median_sorted_arrays([1, 2], [3, 4]) == 2.5
assert find_median_sorted_arrays([], [1]) == 1.0
assert find_median_sorted_arrays([0, 0], [0, 0]) == 0.0
print("ok")
time, space.
Common mistakes & interview follow-ups
- "What is the worst case of your quickselect, and how do you fix it?" when pivots are consistently extreme. Random pivots make it vanishingly unlikely for any fixed input; introselect or median of medians makes it impossible. Mention three-way partitioning for duplicates in the same breath.
- "Prove it is linear on average." Give the phase argument: a pivot in the middle half has probability , shrinks the window to , so the expected work is a geometric series .
- "Why does median of medians use groups of 5?" Because at least elements are guaranteed on each side, so the two recursive calls total and the work is a geometric series. With groups of 3 the calls total and the analysis gives .
- "Heap or quickselect?" Heap if the data is a stream, does not fit in memory, or is tiny; quickselect for a static in-memory array, especially when is near . State both complexities: vs expected .
- "What if the array is distributed across 100 machines?" For top-: each machine returns its local top , the coordinator selects from candidates. For the exact median: rounds of distributed partitioning around a broadcast pivot (only counts travel), or an approximate quantile sketch merged centrally.
- "What if you need the median after every insertion?" Two heaps, per insert. With deletions too: an order-statistic tree or a Fenwick tree over compressed values.
- "What if memory is and the data arrives once?" Bounded heap, or the buffer with periodic quickselect for amortised per element.
- "Why not just sort?" At elements sorting costs about 27 comparisons per element versus about 3. For , sorting is clearer and fast enough; say so.
Quick quiz
1. Quickselect is run with a uniformly random pivot on an already-sorted array of distinct elements. What is its expected running time?
Answer
. The expectation is over the pivot choices, not over the input, so the input order is irrelevant. A fixed pivot rule (first or last element) would be on this input.
2. In median of medians with groups of 5, why is the recursive side at most about ?
Answer
At least half of the group medians are the pivot, and each such group has 3 elements the pivot (its median and the two above), so about elements are the pivot; symmetrically are it. The side we keep excludes one of these sets, leaving at most (plus a small additive constant for partial groups).
3. You need the 10 largest values from a 2 TB log file on a machine with 8 GB of RAM. What do you use and what does it cost?
Answer
A min-heap of size 10, streaming through the file once: time, memory in terms of . Quickselect would need the data in memory (or many passes).
4. Values 2, 5, 9 have weights 1, 1, 3. What is the weighted median, and what does it minimise?
Answer
Total weight 5, half is 2.5. Cumulative weights in sorted order are 1, 2, 5, so the cumulative weight first reaches 2.5 at value 9. It minimises : at the cost is ; at it is .
5. Why does std::nth_element in libstdc++ have an worst case even though median of medians is ?
Answer
It is introselect with a heap-select fallback rather than a median-of-medians fallback. The standard only requires linear time on average, and the heap fallback is simpler and fast enough in practice; the worst case is then instead of quadratic.
Further reading
- C. A. R. Hoare, "Algorithm 65: Find", Communications of the ACM 4(7), 1961 — the original quickselect.
- M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, "Time bounds for selection", Journal of Computer and System Sciences 7(4):448–461, 1973 — median of medians.
- R. W. Floyd and R. L. Rivest, "Expected time bounds for selection" and "Algorithm 489: The algorithm SELECT", Communications of the ACM 18(3), 1975.
- D. R. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 1997 — introsort and introselect.
- D. Dor and U. Zwick, "Selecting the median", SIAM Journal on Computing 28(5), 1999.
- K. Chen and A. Dumitrescu, "Select with groups of 3 or 4", WADS 2015.
- CLRS, Introduction to Algorithms, 3rd ed., Chapter 9 (Medians and Order Statistics; §9.2 randomized select, §9.3 worst-case linear select, Problem 9-2 weighted median) and §14.1 (order-statistic trees). In the 4th edition these are Chapter 9 and §17.1.
- R. Sedgewick and K. Wayne, Algorithms, 4th ed., §2.3 (quicksort, three-way partitioning, selection) and §2.4 (priority queues).
- D. E. Knuth, "Mathematical analysis of algorithms", Proc. IFIP Congress 1971 (the exact average-case analysis of FIND quoted above), and The Art of Computer Programming, Vol. 3, §5.3.3 (minimum-comparison selection).
- cp-algorithms: K-th order statistic in O(N).
- M. Greenwald and S. Khanna, "Space-efficient online computation of quantile summaries", SIGMOD 2001; Z. Karnin, K. Lang, E. Liberty, "Optimal quantile approximation in streams", FOCS 2016.
- Archon: Quick Sort (partition schemes), Heap Sort, Binary Search Mastery (binary search on the answer), Heaps & Priority Queues, Balanced BSTs, Fenwick Trees, Probabilistic Data Structures, Probability for Engineers.
Module 2 navigation. Previous: Other Searches: Ternary, Exponential, Interpolation, Meet-in-the-Middle. Next: Capstone: A Sorting Library With Benchmarks. Module overview: Searching & Sorting. Course home: DSA: Zero to Mastery.