Partitioning & Quickselect

At a glance

The instinct

A partition step puts the pivot at the exact index it would occupy in sorted order: everything smaller to its left, everything larger to its right. If that index is the rank you want, you are done. If not, the answer is on one side, so you throw the other side away. Each round discards about half the remaining work, so the expected total is n + n/2 + n/4 + ... ≈ 2n - linear time without ever sorting. That is the engine behind Kth Largest Element in an Array.

Partitioning is also useful on its own. Sort Colors is a three-way partition around the value 1: zeros to the left, twos to the right, ones in between, in a single pass.

Recognise it

Not this pattern if...

• Data arrives as a stream or you need the k-th largest after every insertion - keep a heap of size k.
• You need the k results sorted, or the original relative order preserved - sort, or use a heap.
• The array is already sorted - just index into it.
• The input must not be modified - quickselect rearranges it in place, so copy it or use a heap.

Memory hack

Analogy - finding the 10th tallest person in a crowd. Point at someone at random and say "shorter people step left, taller people step right". Count the right-hand group. If exactly 9 people are taller, the person you pointed at is your answer. If 30 are taller, send the left group home and repeat with the tall group. You never need to line everyone up by height.

Say it out loud:

1. "Convert the request to an index: the k-th largest is index n - k in ascending order."
2. "Random pivot, partition, and the pivot lands at p."
3. "If p equals the target I'm done; if p is smaller go right, otherwise go left. Expected O(n), worst case O(n²), which the random pivot makes very unlikely."

How it works

Find the 2nd largest in [3, 2, 1, 5, 6, 4]: n = 6, so the target index is 6 - 2 = 4. For a readable trace the pivot is the last element (the template randomises it):

The three-way partition keeps four regions with three pointers: [0, low) is "less than pivot", [low, i) is "equal", [i, high] is "not yet seen" and (high, end] is "greater". Each step shrinks the unseen region by one.

Java template

import java.util.concurrent.ThreadLocalRandom;

class QuickselectTemplate {
    // k-th largest (1-based) = the element at index n - k in ascending order.
    static int kthLargest(int[] a, int k) {
        int target = a.length - k, lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;     // answer lies to the right
            else hi = p - 1;                // answer lies to the left
        }
    }

    // Lomuto partition with a random pivot; returns the pivot's final (sorted) index.
    static int partition(int[] a, int lo, int hi) {
        swap(a, lo + ThreadLocalRandom.current().nextInt(hi - lo + 1), hi);
        int pivot = a[hi], store = lo;
        for (int j = lo; j < hi; j++) {
            if (a[j] < pivot) swap(a, store++, j);  // grow the "smaller than pivot" block
        }
        swap(a, store, hi);
        return store;
    }

    // Three-way (Dutch national flag) partition: < pivotValue | == pivotValue | > pivotValue.
    static void threeWay(int[] a, int pivotValue) {
        int low = 0, i = 0, high = a.length - 1;
        while (i <= high) {
            if (a[i] < pivotValue) swap(a, low++, i++);
            else if (a[i] > pivotValue) swap(a, i, high--); // don't advance i: the swapped-in value is unseen
            else i++;
        }
    }

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Sort Colors is simply threeWay(nums, 1). If the input may contain many equal values, use the three-way split inside quickselect too: when the target index falls in the "equal" block you can stop immediately.

Complexity

Variations

• Binary partition by predicate - two pointers, one write position; e.g. moving zeros or separating even and odd numbers.
• Three-way partition - low / mid / high pointers. Sort Colors.
• Selecting a rank - random-pivot quickselect. Kth Largest Element in an Array.
• Top-k by a derived key - select on distance or frequency, then take the left block; e.g. k closest points or top k frequent elements.
• Hoare partition - two pointers moving inward, fewer swaps, but it returns a split point rather than the pivot's final index.
• Counting instead of partitioning - when values come from a tiny range (just 0, 1, 2), two passes of counting also work.

Common mistakes

• Off-by-one when converting "k-th largest" to an index: it is n - k in ascending order, not k or n - k - 1.
• Advancing i after swapping with high in the three-way partition - the value that just arrived has not been examined yet.
• Recursing into both sides "to be safe" - that is quicksort, and the cost jumps to O(n log n).
• Treating Hoare's return value as the pivot's final position; only Lomuto (as written above) guarantees that.
• Forgetting that the input array is rearranged; copy it first if the caller still needs the original order.

All practice problems

2 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.