What is the Quickselect Algorithm?
Learn how the quickselect algorithm finds the k-th smallest element in average O(n) time and how to answer this interview question.
Expected Interview Answer
Quickselect is a selection algorithm that finds the k-th smallest (or largest) element in an unsorted array in average O(n) time by reusing quicksort's partition step but recursing into only one side instead of both.
Like quicksort, quickselect picks a pivot, partitions the array so smaller elements land left and larger elements land right, and then checks where the pivot's final index falls relative to k. If the pivot lands exactly at k, that element is the answer; otherwise the algorithm recurses only into the half that must contain the k-th element, discarding the other half entirely. Because only one side is ever explored, the expected work forms a shrinking geometric series that sums to O(n) rather than quicksort's O(n log n). The worst case is still O(n²) with a consistently poor pivot, so real implementations use random or median-of-medians pivot selection to keep the average-case guarantee reliable.
- Average O(n) time, faster than full sort for a single query
- In-place partitioning, O(1) extra space beyond recursion
- Directly answers k-th smallest/largest and median queries
- Foundation for Python heapq.nsmallest-style top-K solutions
AI Mentor Explanation
Quickselect is like a selector trying to find the 5th fastest bowler in a trial without ranking every bowler in the squad. The selector picks one bowler's pace as a benchmark, splits the group into slower and faster piles, and only cares whether the 5th spot fell inside the faster pile or the slower pile. Whichever pile contains the target rank gets re-split with a new benchmark; the other pile is ignored completely and never touched again. This selective narrowing is why the selector reaches the exact 5th-fastest bowler in far fewer comparisons than sorting the whole squad by pace.
Step-by-Step Explanation
Step 1
Pick a pivot
Choose an element (ideally random) from the current subarray as the pivot.
Step 2
Partition around it
Rearrange in place so smaller elements land left of the pivot and larger elements land right, like quicksort.
Step 3
Compare pivot index to k
If the pivot's final index equals k, it is the answer; otherwise recurse into only the side containing k.
Step 4
Repeat on the shrinking subarray
Discard the other side entirely; average total work sums to O(n) across all recursive calls.
What Interviewer Expects
- Explain reuse of the quicksort partition step
- State average O(n) vs worst case O(n²), and how random pivots mitigate it
- Explain why only one side is recursed into, unlike quicksort
- Name use cases: median finding, top-K, percentile queries
Common Mistakes
- Confusing quickselect with full quicksort and recursing into both sides
- Forgetting the O(n²) worst case with a bad pivot strategy
- Not knowing it can find k-th smallest or largest with a minor tweak
- Assuming it returns a sorted array instead of just the k-th element
Best Answer (HR Friendly)
“Quickselect is a shortcut for finding just the k-th smallest item in a list without sorting the whole thing. It reuses the same partitioning trick as quicksort, but only follows the half of the data that could contain the answer, which makes it much faster than a full sort when I only need one specific rank.”
Code Example
import random
def quickselect(nums, k):
"""Return the k-th smallest element (0-indexed) in nums."""
lo, hi = 0, len(nums) - 1
while True:
if lo == hi:
return nums[lo]
pivot_idx = random.randint(lo, hi)
pivot_idx = partition(nums, lo, hi, pivot_idx)
if k == pivot_idx:
return nums[k]
elif k < pivot_idx:
hi = pivot_idx - 1
else:
lo = pivot_idx + 1
def partition(nums, lo, hi, pivot_idx):
pivot = nums[pivot_idx]
nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
store = lo
for i in range(lo, hi):
if nums[i] < pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return storeFollow-up Questions
- How would you find the median of an unsorted array using quickselect?
- How does random pivot selection reduce the risk of the O(n²) worst case?
- How would you find the k largest elements instead of the k-th smallest?
- When would a heap-based top-K approach be preferable to quickselect?
MCQ Practice
1. What is the average-case time complexity of quickselect?
Because only one partitioned side is recursed into, the expected work forms a shrinking series summing to O(n).
2. How does quickselect differ from quicksort after partitioning?
Quickselect discards the side that cannot contain the k-th element and only recurses into the relevant side.
3. What is quickselect's worst-case time complexity?
A consistently poor pivot choice can degrade quickselect to O(n²), just like quicksort.
Flash Cards
What does quickselect find? — The k-th smallest (or largest) element in an unsorted array.
What is quickselect's average time complexity? — O(n), because it recurses into only one side after partitioning.
What algorithm does quickselect reuse for partitioning? — Quicksort's partition step around a chosen pivot.
How is the O(n²) worst case mitigated? — Using random or median-of-medians pivot selection.