Quick Select · Kth Largest

Find the Kth largest without fully sorting. Partition around a pivot, then recurse into only the side that must contain the answer, throwing the other half away each time.

Concept

Partition, then pick a side

Partition puts the pivot in its final sorted slot: everything smaller left, larger right. If that slot is exactly the target index, done. Otherwise recurse into only the half that holds the target.

Why it beats sorting

Kth largest = index n-k when sorted ascending
Each partition fixes one element's true position
Discard the useless half, don't recurse both
Average O(n), not O(n log n)

Interactive

Zero in on the target index

Out of range Pivot < pivot ≥ pivot / scanning Answer

Array k (largest)

slowfast

Step 0

Target index

–

Pivot slot

–

Range size

–

Answer

Implementation

C++

int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[hi], i = lo;          // Lomuto: pivot = last
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);                    // pivot to its final slot
    return i;
}

int quickSelect(vector<int>& a, int lo, int hi, int target) {
    if (lo == hi) return a[lo];
    int p = partition(a, lo, hi);
    if (p == target) return a[p];        // pivot IS the answer
    if (target < p) return quickSelect(a, lo, p - 1, target);
    return quickSelect(a, p + 1, hi, target);   // one side only
}

int findKthLargest(vector<int>& a, int k) {
    return quickSelect(a, 0, a.size() - 1, a.size() - k);
}

Complexity

Time (avg)

O(n)

Each step halves the range: n + n/2 + n/4 + … ≈ 2n.

Time (worst)

O(n²)

Pathological pivots. Random or median-of-medians pivot avoids it.

Space

O(1)

In-place partition; recursion tail-optimizes to iterative.

Notes

Recurse one side, not two. That's the difference from quicksort, and why the average drops from O(n log n) to O(n).
Kth largest → index n-k in ascending order. Sort the mapping once and the rest is pure selection.
Worst case O(n²) hits when the pivot is always the min/max. Randomize the pivot to make that astronomically unlikely.
A max-heap gives O(n log k) and is simpler if k is tiny; quickselect wins on average for arbitrary k.
Median-of-medians guarantees worst-case O(n) but with a big constant, rarely worth it in practice.