core practice · coding problem
k-th smallest by quickselect
Implement kthSmallest(nums, k) returning the k-th smallest (k is 1-based) using quickselect — partition, then recurse into only ONE side. Do not sort the array and do not mutate the caller's input.
The mechanism
Quicksort recurses into both halves; quickselect knows which half holds the answer and discards the other, so the work is n + n/2 + n/4 … which sums to O(n) rather than O(n log n). The catch is that the guarantee is only expected: adversarial or already-sorted input with a naive pivot degrades to O(n²), which is what randomised pivots and median-of-medians exist to prevent.
Expected evidence
kthSmallest([7,10,4,3,20,15], 3) -> 7
Try this drill in the practice workspace →
Hints when you need them
- After partitioning, compare k against the size of the left partition to decide which side can possibly hold the answer.
- Recursing into both sides makes this quicksort — the whole saving is discarding one.
Watch for these mistakes
- Quoting O(n) as worst case — it is expected; the worst case is quadratic without a good pivot rule
- Reaching for a full sort when only one order statistic is needed
- Off-by-one between the k-th smallest and index k after partitioning
- Using a size-k heap for large k, where quickselect is cheaper, or quickselect for streaming data, where it does not apply