Quick Select

How to think about it

Quick select is quicksort that only recurses into one half. Pick a pivot, partition the array so elements below the pivot are left and above are right. The pivot lands at its sorted position p. If p === k, you are done. If p < k, recurse right; if p > k, recurse left. Each step discards roughly half the array, giving O(n) average, far cheaper than the O(n log n) full sort.

The enemy is the worst case O(n²): a bad pivot (e.g. always the first element on an already-sorted input) shrinks the array by one each step. A randomized pivot makes this exponentially unlikely. For top-K where K is small relative to N, a heap (O(n log k)) can beat quick select, but quick select wins when K is a fraction of N or you need a single order statistic.

Template shapes

Shape	Core move	Example
kth smallest	Partition, recurse into the half containing k	LC 215, LC 378
Top K	Quick select to rank K, slice left partition	LC 347, LC 973
Streaming top K	Heap (not quick select), select beats on the root	LC 703
Median	Quick select to n/2 (or two selects for even n)	,

Complexity baseline

O(n) average time, O(n²) worst case (mitigated by random pivot). O(1) extra space (in place). Recursion depth O(log n) average. For streaming top-K or tiny K, prefer a heap at O(n log k).

From template to problem

1. Clarify k: 0-indexed or 1-indexed? Smallest or largest (flip comparison)?
2. Choose a pivot strategy, randomized is the safe default.
3. Partition into [< pivot | pivot | > pivot] and compare pivot index to k.
4. Recurse into only the side that contains k; return when found.
5. For top-K, quick select to the Kth element then slice, or use a heap if K is tiny.

/** Quick select template: kth smallest (0-indexed) via randomized partition. */

export function quickSelect(nums: number[], k: number): number {
  return select(nums, 0, nums.length - 1, k);
}

function select(nums: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return nums[lo]!;
  const pivotIdx = partition(nums, lo, hi);
  if (k === pivotIdx) return nums[k]!;
  if (k < pivotIdx) return select(nums, lo, pivotIdx - 1, k);
  return select(nums, pivotIdx + 1, hi, k);
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

/** Quick select template: kth smallest (0-indexed) via randomized partition. */

export function quickSelect(nums: number[], k: number): number {
  return select(nums, 0, nums.length - 1, k);
}

function select(nums: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return nums[lo]!;
  const pivotIdx = partition(nums, lo, hi);
  if (k === pivotIdx) return nums[k]!;
  if (k < pivotIdx) return select(nums, lo, pivotIdx - 1, k);
  return select(nums, pivotIdx + 1, hi, k);
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}