148. Quickselect Kth Statistic

Why this mechanism works

Selection needs only the partition containing the target rank, not both sorted sides. Three-way partitioning identifies an entire equal-pivot rank band. If the target falls inside that band, its value is known immediately; otherwise discard the band and the irrelevant side.

State and boundaries

target is a zero-based rank in the copied array. [left,right) contains that rank's unresolved region. [low,high) is the equal-pivot band after partition.

Protocol

1. Translate k to an ascending target rank.
2. Choose a random pivot value in the candidate interval.
3. Partition into less, equal and greater regions.
4. Keep only the side containing target.
5. Return pivot when target lies in the equal region.

Visualization

[ values < p | values == p | values > p ]
             low          high
target in [low,high) -> answer p

Python implementation

import random

def quickselect(nums, k, largest=False):
    values = list(nums)
    target = len(values) - k if largest else k - 1
    left, right = 0, len(values)
    while left < right:
        pivot = values[random.randrange(left, right)]
        low = scan = left
        high = right
        while scan < high:
            if values[scan] < pivot:
                values[low], values[scan] = values[scan], values[low]
                low += 1
                scan += 1
            elif values[scan] > pivot:
                high -= 1
                values[scan], values[high] = values[high], values[scan]
            else:
                scan += 1
        if target < low:
            right = low
        elif target >= high:
            left = high
        else:
            return pivot

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 quickselect: values = list(nums)
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]

L5 quickselect: target = len(values) - k if largest else k - 1
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4

L6 quickselect: left, right = 0, len(values)
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6

L8 quickselect: pivot = values[random.randrange(left, right)]
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6; pivot=4

L9 quickselect: low = scan = left
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6; pivot=4; low=0; scan=0

L10 quickselect: high = right
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6; pivot=4; low=0; scan=0; high=6

L14 quickselect: low += 1
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6; pivot=4; low=1; scan=0; high=6

L15 quickselect: scan += 1
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 5, 6, 4]; target=4; left=0; right=6; pivot=4; low=1; scan=1; high=6

... 17 intermediate state changes omitted ...

L8 quickselect: pivot = values[random.randrange(left, right)]
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 4, 5, 6]; target=4; left=4; right=5; pivot=5; low=5; scan=6; high=6

L9 quickselect: low = scan = left
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 4, 5, 6]; target=4; left=4; right=5; pivot=5; low=4; scan=4; high=6

L10 quickselect: high = right
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 4, 5, 6]; target=4; left=4; right=5; pivot=5; low=4; scan=4; high=5

L20 quickselect: scan += 1
nums=[3, 2, 1, 5, 6, 4]; k=2; largest=True; values=[3, 2, 1, 4, 5, 6]; target=4; left=4; right=5; pivot=5; low=4; scan=5; high=5

L4 quickselect: values = list(nums)
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]

L5 quickselect: target = len(values) - k if largest else k - 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2

L6 quickselect: left, right = 0, len(values)
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2; left=0; right=4

L8 quickselect: pivot = values[random.randrange(left, right)]
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2; left=0; right=4; pivot=2

L9 quickselect: low = scan = left
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2; left=0; right=4; pivot=2; low=0; scan=0

L10 quickselect: high = right
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2; left=0; right=4; pivot=2; low=0; scan=0; high=4

L20 quickselect: scan += 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[2, 1, 2, 3]; target=2; left=0; right=4; pivot=2; low=0; scan=1; high=4

L13 quickselect: values[low], values[scan] = values[scan], values[low]
nums=[2, 1, 2, 3]; k=3; largest=False; values=[1, 2, 2, 3]; target=2; left=0; right=4; pivot=2; low=0; scan=1; high=4

L14 quickselect: low += 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[1, 2, 2, 3]; target=2; left=0; right=4; pivot=2; low=1; scan=1; high=4

L15 quickselect: scan += 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[1, 2, 2, 3]; target=2; left=0; right=4; pivot=2; low=1; scan=2; high=4

L20 quickselect: scan += 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[1, 2, 2, 3]; target=2; left=0; right=4; pivot=2; low=1; scan=3; high=4

L17 quickselect: high -= 1
nums=[2, 1, 2, 3]; k=3; largest=False; values=[1, 2, 2, 3]; target=2; left=0; right=4; pivot=2; low=1; scan=3; high=3

Why the solution is correct

Partition places all smaller values before the equal band and all larger values after it, establishing the band's exact rank interval within the unresolved range. The target value must lie in the selected band or side, so discarding other regions is safe. The retained region strictly shrinks unless the answer is returned.

Time and space

Expected O(n) time with randomized pivots and O(n^2) worst case; O(n) copy storage and O(1) partition state. Three-way partition handles duplicate bands directly.

Common mistakes

Using k as a zero-based index shifts the rank. Recursing into both sides turns selection back into sorting work.

Reasoning card

Transfer exercise

Select several quantiles together and discuss when reusing partitions is better than running independent selections.