Divide and conquer · HTML
Convert the request to zero-based ascending target. After partition(lo,hi), pivot rests at p with values <= pivot on the left and > pivot on the right. Return at p=target; otherwise discard the opposite side permanently.
Recognition signals
- Only a kth smallest/largest, median, or rank boundary is needed.
- The input supports random access and may be reordered.
- The first k items need not be sorted.
- A full O(n log n) sort should be avoided.
- Expected complexity from randomized pivots is acceptable.
False friends
| Signal | Why it is different |
|---|
| An online stream | Future arrivals change ranks; use a bounded heap or two heaps. |
| A strict worst-case requirement | Ordinary Quickselect can take O(n²); choose a heap or deterministic pivot strategy. |
| Stable complete ordering | Partition mutates order and is not stable; sorting is the proper deliverable. |
Core invariant
The target rank remains inside current closed interval [lo,hi]. Each partition finalizes the pivot rank, allowing the side without target to be discarded.
State, transition, and processing order
| Item | Definition |
|---|
| State | A mutable array, lo/hi bounds, zero-based target rank, and randomized pivot. |
| Transition | Partition to p; set lo=p+1 when p<target, hi=p-1 when p>target, and return on equality. |
| Frontier / order | One contiguous range that can still contain the rank; unlike Quicksort, the other partition is never processed. |
Python skeleton
from random import randrange
def kth_smallest(nums, k):
if not 1 <= k <= len(nums): raise ValueError('k')
a, target = list(nums), k - 1
lo, hi = 0, len(a) - 1
while lo <= hi:
q = randrange(lo, hi + 1)
a[q], a[hi] = a[hi], a[q]
pivot, p = a[hi], lo
for i in range(lo, hi):
if a[i] <= pivot:
a[p], a[i] = a[i], a[p]; p += 1
a[p], a[hi] = a[hi], a[p]
if p == target: return a[p]
if p < target: lo = p + 1
else: hi = p - 1
Correctness sketch
- Partition leaves every left value <= pivot and every right value > pivot, giving pivot a valid final rank p.
- If target<p it cannot lie at p or to the right; the symmetric argument holds for target>p.
- The interval strictly shrinks without discarding target, so equality returns the correct order statistic.
Complexity
| Time | Space | Parameters |
|---|
| Expected O(n) with random pivots; worst case O(n²) | O(1) in-place iterative; the sample copies input in O(n) | n is size and k is 1-based; duplicates affect partition balance. |
Edge cases
- k outside range
- empty input
- many duplicates
- sorted or reverse-sorted input
- whether mutation is allowed
- converting kth-largest rank
Error patterns
| Pattern | Why it fails / fix |
|---|
| Rank indexing errors | Kth-smallest uses target=k-1; kth-largest uses target=n-k. |
| Mismatched partition contract | Fix closed bounds, equality placement, and pivot's final position before shrinking. |
| Searching both sides like Quicksort | Only one side contains target; processing both loses selection's advantage. |
| A consistently bad pivot | Ordered input can trigger O(n²); randomize or use a robust pivot. |
Selection and exclusion rules
- Use Quickselect for one offline rank when reordering is allowed.
- Use heaps or sorting for streaming or a stable worst-case bound.
- Normalize every request to an ascending zero-based target.
- Consider three-way partitioning with many duplicates.
Original micro-example
| Part | Detail |
|---|
| Result | The next partition locates 4 without fully ordering the array. |
| Setup | For readings [8,2,6,4], find the second smallest. |
| Trace | A pivot of 6 lands at p=2; target=1, so only [2,4] remains. |
Recall prompts
My notes