templates · Linked lists, sorting & selection

Quickselect (k-th smallest or largest)

  • "Find the k-th largest (or smallest)" and you only need that one value, not a full sort
  • "The k closest points" or "the top k", in any order, in average O(n)
  • You need the median of an unsorted array

Quickselect

the one rule

The invariant

After partition returns p, everything left of p is smaller than a[p] and nothing right of it is, so a[p] sits at its sorted index.

write it from memory

The template

javajava.util.*
private static final Random RANDOM = new Random(); /** The k-th largest value (k = 1 is the max). Rearranges nums. */static int kthLargest(int[] nums, int k) {    int target = nums.length - k;                 // its index in ascending order    int lo = 0, hi = nums.length - 1;    while (lo < hi) {        int p = partition(nums, lo, hi);        if (p == target) break;                   // the pivot landed exactly there        if (p < target) lo = p + 1;               // keep only the side that holds target        else hi = p - 1;    }    return nums[target];} /** Lomuto partition around a random pivot: smaller values go left, and the pivot's final index is returned. */static int partition(int[] a, int lo, int hi) {    swap(a, lo + RANDOM.nextInt(hi - lo + 1), hi); // random pivot avoids the O(n²) trap    int pivot = a[hi];    int store = lo;    for (int i = lo; i < hi; i++) {        if (a[i] < pivot) swap(a, i, store++);    // what counts as "smaller"    }    swap(a, store, hi);                           // pivot goes to its sorted place    return store;} static void swap(int[] a, int i, int j) {    int t = a[i];    a[i] = a[j];    a[j] = t;}

It is quicksort that only goes into one side. Compare p with the target index and drop the other half.

fill in the blanks — only these lines change per problem

  1. line 5Which sorted index you want: n - k for the k-th largest, k - 1 for the k-th smallest.
  2. line 22The "smaller" rule. For points, compare distances (x*x + y*y), not the raw values.
  3. line 18Pivot choice. Keep it random; the first or last element gives O(n²) on sorted input.

complexity

What it costs

time O(n) average, O(n²) worst
Each round keeps one side only: about n + n/2 + n/4 + … ≈ 2n steps on average. A very unlucky pivot every round keeps n − 1 elements each time, which is O(n²); the random pivot makes that extremely unlikely, unless many values are equal (see the bugs).
space O(1)
It works inside the array with a loop, not recursion, so there is no call stack to grow.

watch out

Common bugs

  • Trusting the random pivot with many equal values. With this < partition, an array of all-equal values still costs O(n²); a three-way partition (less / equal / greater) fixes it.
  • Mixing up the index: the k-th largest is index n - k in ascending order, not k.
  • Saying it is O(n) in the worst case. Say average O(n), worst O(n²), and why.

use it

Practise it on

learn it properly