Quickselect
Overview
A selection algorithm to find the k-th smallest element in an unordered list, combining the partitioning from Quicksort with the halving strategy of Binary Search.
It achieves O(n) average time complexity, which is theoretically optimal for finding a single order statistic.
Where used: Finding the median of an array without fully sorting it, Top-K algorithms (when you don't need the top K elements sorted among themselves)
Why it exists
Problem: We want to find the k-th smallest (or largest) element in an unsorted array. Sorting the whole array takes O(n log n). Using a heap takes O(n log k). Can we do it in linear time O(n)?
Naive approach: Sort the array and return `arr[k]`, taking O(n log n) time.
Better idea: Use Quicksort's partition step! If the pivot lands exactly at index k, we're done. If it lands before k, we only recurse on the right half. If it lands after k, we only recurse on the left half.
Why learn this
- It teaches you how to optimize divide-and-conquer by pruning unnecessary recursive branches.
- It's a classic follow-up in interviews when you propose an O(n log n) sorting solution for a Top-K problem.
Mental model
It's binary search mixed with Quicksort. Partition the array around a pivot. The pivot's final index tells us which half contains the k-th element, so we throw away the other half entirely.
Partition the array exactly like in Quicksort. The pivot ends up at index `p`. If `p == k`, return the pivot. If `p < k`, the answer must be in the right partition. If `p > k`, the answer is in the left partition. Because we only recurse into one side, the average size of the subarray halves each time.
Repeated decision: Did the pivot land on the target index k? If not, do I need to search the left partition or the right partition?
Deep dive
Quickselect borrows the `partition` subroutine directly from Quicksort. Remember that `partition` picks a pivot and places it in its final sorted position, say index `p`. All elements to the left are smaller, and all elements to the right are larger.
If we want the `k`-th smallest element (which corresponds to index `k` in a 0-indexed sorted array), we can just look at `p`.
- If `p == k`: The pivot is the `k`-th smallest element! We found it.
- If `p > k`: The element we want is in the left subarray. We recursively call Quickselect on the left.
- If `p < k`: The element we want is in the right subarray. We recursively call Quickselect on the right.
In Quicksort, we recurse on *both* halves. In Quickselect, we only recurse on *one* half. This makes a massive difference in time complexity. Instead of doing `n + n/2 + n/4 ...` work on all branches, we only do work on one branch. The sum of the series `n + n/2 + n/4 + ...` converges to `2n`, which is `O(n)`.
Like Quicksort, Quickselect has a worst-case time complexity of `O(n^2)` if we repeatedly pick the worst possible pivot (e.g., the largest element every time). To prevent this in practice, we pick a random pivot.
Key points
- Complexity: Average Time is O(n). Worst-case Time is O(n^2). Space is O(1) if implemented iteratively (or O(log n) average if recursive).
- In-place but mutates: It operates in-place, meaning it uses O(1) auxiliary space, but it scrambles the original array.
Pattern: Quickselect / Pruned Partitioning
Recognition cues:
- Find the k-th largest/smallest element
- Find the median of an unsorted array
Failure signals
- The array is immutable or you cannot mutate the input (Quickselect partitions in-place).
Engineering examples
Median finding in standard libraries
C++ std::nth_element finds the element that would be at the nth position if the array were sorted.
It uses Introselect (a hybrid of Quickselect and Median of Medians) to guarantee O(n) performance without fully sorting.
When not to use
- Streaming data: If data is arriving continuously and you need to keep track of the running median or top K, Quickselect is useless. Use a Heap instead.
Common mistakes
- Translating Kth largest to an index: If a problem asks for the 'k-th largest' element, that corresponds to the index `len(arr) - k` if the array was sorted in ascending order. Failing to convert this index correctly leads to the wrong answer.
- Forgetting that the Top K aren't sorted: Quickselect can find the k-th element, and as a side effect, all elements to its left are smaller. However, those smaller elements are NOT sorted. If the problem requires the top K elements in sorted order, you must sort them afterward (which takes O(k log k)).
Recall questions
- What is the average and worst-case time complexity of Quickselect?
- Why is Quickselect O(n) on average while Quicksort is O(n log n)?
- If we want the K-th LARGEST element in an array of size N, what 0-indexed position do we target in ascending Quickselect?
Understanding checks
If you are looking for the median (index n/2) and the first partition step places the pivot at index n/4, which half do you search next?
The right half.
The target index (n/2) is greater than the pivot index (n/4), so the element we want must be among the elements larger than the pivot.
A developer writes `return quickselect(arr, k)` but it fails for 'find the 2nd largest element'. Why?
They didn't convert 'k-th largest' to the correct 0-indexed position. It should be `quickselect(arr, len(arr) - k)`.
Quickselect, by default, partitions smaller elements to the left and larger to the right, finding the k-th SMALLEST element.
Questions & answers
Kth Largest Element in an Array
Use Quickselect targeting index `len(nums) - k`. A heap is also acceptable, but Quickselect provides O(n) average time vs O(n log k) for a heap.
Approach: Implement standard partition, then conditionally recurse left or right.
Practice tasks
Kth Largest Element in an Array
Given an integer array `nums` and an integer `k`, return the `kth` largest element in the array. Can you solve it without sorting in O(n) time?
Continue learning
Previous: Quicksort & partition