Divide & Conquer

QuickSelect

Find the Kth smallest element without fully sorting. Pick a pivot, partition the array. If K falls in the left partition, recurse left; if right, recurse right. Expected O(n) because you only recurse into ONE half.

O(n) average

O(1)

How It Works

QuickSelect finds the kth smallest element without sorting everything. Pick a pivot and partition the array so smaller elements sit to its left and larger to its right; the pivot lands in its final sorted position. If that position equals k, done. Otherwise recurse only into the side that contains index k — the other side is irrelevant, which is the crucial divergence from quicksort.

Recursing into one side turns the cost sum into n + n/2 + n/4 + ... = O(n) expected time with a random pivot, versus O(n log n) for a full sort. The worst case is O(n^2) when pivots are consistently bad, though random pivot selection makes that vanishingly unlikely, and the median-of-medians pivot rule guarantees O(n) at a higher constant factor. Partitioning is in place, so space is O(1) with an iterative loop. It is the standard answer to kth-largest and top-k problems when a heap's O(n log k) is not required.

Step-by-Step Visualization

QuickSelect: find 4th smallest (k=3)

Pivot4

1/2

Code

Java

static int quickSelect(int[] arr, int k, int lo, int hi) {
  int pivot = arr[hi];
  int i = lo;
  for (int j = lo; j < hi; j++)
    if (arr[j] <= pivot) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; }
  int tmp = arr[i]; arr[i] = arr[hi]; arr[hi] = tmp;

  if (i == k) return arr[i];
  return i < k ? quickSelect(arr, k, i + 1, hi) : quickSelect(arr, k, lo, i - 1);
}

Tips & Gotchas

1Find kth element without fully sorting

2Partition around pivot, recurse into the relevant half only

3Average O(n) but worst case O(n²) — use random pivot

Practice Problems

1Kth Largest Element in an Array
2K Closest Points to Origin
3Top K Frequent Elements
4Wiggle Sort II

About the Divide & Conquer Pattern

Split the problem into two (or more) smaller subproblems, solve each independently, then combine the results. The splitting usually halves the input, giving O(n log n) algorithms.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

QuickSelect or a heap for kth largest — how do I choose?

QuickSelect gives O(n) expected time and O(1) space but mutates the array and has an unlikely O(n^2) worst case. A size-k min-heap runs in O(n log k), never degrades, preserves the input, and works on streams where you cannot hold all data. For static in-memory arrays QuickSelect is usually faster; for streaming or adversarial inputs pick the heap.

Why is QuickSelect expected O(n) when quicksort is O(n log n)?

Quicksort must recurse into both partitions, paying O(n) at every one of log n levels. QuickSelect discards one partition entirely each round, so the work forms a geometric series n + n/2 + n/4 + ... that sums to O(n).

How do I avoid the quadratic worst case on adversarial or sorted input?

Choose the pivot uniformly at random, or shuffle the array once up front, making bad pivot sequences astronomically improbable. If a hard guarantee is required, the median-of-medians strategy selects pivots deterministically for worst-case O(n), though its constants make it rare in practice.