Quickselect Algorithm: Find the Kth Largest Element
Quickselect is the algorithm you reach for when a problem asks for the kth largest or kth smallest element and a full sort feels like overkill. It runs in O(n) average time by reusing the partition step from quicksort, but instead of recursing into both halves it throws away the half that cannot contain the answer and recurses into only the other one. Sorting an entire array to answer a question about a single position is exactly what an interviewer is testing when they ask "can you do better than O(n log n)?", and quickselect is the answer to that prompt. This piece walks through a working Python implementation, the worst case you need to name out loud, and the exact moment in an interview where quickselect beats a heap.
What Is Quickselect, and Why Does It Beat Sorting?
Quickselect finds the kth smallest or kth largest element in an unsorted array without fully sorting it, by running the partition step from quicksort and recursing into only the side that still contains the target position. A full sort spends O(n log n) time putting every element in its final place, even though the question only cares about one of those places. Quickselect skips that waste: it picks a pivot, moves everything smaller to one side and everything larger to the other, checks which side the kth position landed in, then repeats the process on that side alone.
That one change, recursing into one side instead of both, is what separates quickselect from quicksort and drops the average running time from O(n log n) to O(n). Quicksort has to keep splitting every sub-array until each one holds a single element, since it needs the whole array sorted. Quickselect stops the moment the pivot's final resting place matches the index it is looking for, and it never touches the side that cannot hold that index. Each partition pass still costs time proportional to the size of the current sub-array, but because the sub-array shrinks fast (by roughly half, on average, with a reasonably chosen pivot) the total work across every pass sums to a linear function of the original array size instead of a linearithmic one.
The pattern shows up under a small set of phrasings once you know to look for it. Watch for a problem that asks for the kth largest, kth smallest, or median value, or one that explicitly says you don't need the array in sorted order, only a single element's rank within it:
- the phrase "kth largest" or "kth smallest" appears directly in the prompt
- the problem asks for a median or a percentile of an unsorted collection
- there's an explicit follow-up asking for something faster than sorting
- the array can be freely reordered, since quickselect partitions the input in place
That last point matters more than it looks. If a problem needs the original array order preserved, quickselect's in-place partitioning becomes a liability rather than a convenience, and a heap of size k, which reads the array once without reordering it, is often the better fit, a trade-off the comparison section below covers in full.
How Do You Implement Quickselect in Python?
A working quickselect implementation needs three pieces: a partition function that rearranges one sub-array around a pivot, a random pivot choice to avoid the worst case, and a recursive step that narrows the search to one side. Here is a complete version that finds the kth largest element in an array, which is the shape this pattern takes in most real interviews:
import random
def find_kth_largest(nums, k):
target = len(nums) - k # index of kth largest in sorted order
def partition(left, right, pivot_index):
pivot = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def select(left, right):
if left == right:
return nums[left]
pivot_index = random.randint(left, right)
pivot_index = partition(left, right, pivot_index)
if target == pivot_index:
return nums[target]
if target < pivot_index:
return select(left, pivot_index - 1)
return select(pivot_index + 1, right)
return select(0, len(nums) - 1)The partition function does the real work. It moves the pivot to the end, walks the rest of the sub-array once, and swaps every element smaller than the pivot into a growing block at the front. When the walk finishes, the pivot swaps into the boundary between that block and everything larger, which is exactly where it belongs in sorted order. That boundary index is what the select step compares against the target position.
The select step is where the "throw away half the work" idea actually happens. Once it knows the pivot's sorted position, it checks whether that position is the one being searched for, and if not, it recurses into only the side that could still contain it. Choosing the pivot with random.randint instead of always picking the first or last element is not a style preference. It's the difference between an algorithm that runs in linear time on almost any input and one that quietly degrades on inputs an interviewer might hand you on purpose.
What Is the Time and Space Complexity of Quickselect?
Quickselect runs in O(n) average time and O(n²) worst case time, and naming both numbers, along with why the gap between them exists, is worth more to an interviewer than reciting either one alone.
The average case comes from how fast the search space shrinks. With a randomly chosen pivot, the sub-array being searched shrinks by a good fraction on most partition passes, and summing a shrinking geometric series of pass sizes (n, then roughly n/2, then roughly n/4, and so on) adds up to a linear total rather than the n-per-level total that a full sort needs at every one of its O(log n) levels. The worst case happens when the pivot choice is unlucky on every single pass, for example always landing on the smallest or largest remaining element, which shrinks the search space by only one element per pass instead of by half. That degrades the total work to the same shape as a bubble sort: n + (n-1) + (n-2) and so on, which sums to O(n²).
A fixed pivot rule, like always picking the last element, turns that worst case from a rare accident into something an adversarial input can trigger on purpose: a sorted or reverse-sorted array. Picking the pivot at random breaks that pattern, since no fixed input can be constructed in advance to target a pivot the algorithm chooses at runtime. The worst case still exists in theory, but the odds of hitting it on real data drop low enough that it stops being a practical concern, which is exactly the argument to make if an interviewer pushes on it.
Lined up against the alternatives, the gap is easiest to state directly. A full sort costs O(n log n) time, the right choice when simplicity matters more than speed. A min-heap of size k costs O(n log k) time and O(k) space, and wins when k is small or the input arrives as a stream. Quickselect costs O(n) time on average, the fastest of the three whenever the whole array already fits in memory and its order doesn't need to survive the search.
Space complexity is the other number worth stating precisely. The partitioning itself happens in place, so it needs no extra array, but the recursive calls still use stack space, roughly O(log n) on average since the search space keeps halving, growing toward O(n) in the same unlucky scenario that produces the O(n²) time. An iterative version with an explicit stack avoids the call-stack growth but doesn't change the underlying time bounds, and most interviewers are satisfied with the recursive version as long as you can name that trade-off when asked.
How Do You Solve "Kth Largest Element in an Array" With Quickselect?
Kth Largest Element in an Array, LeetCode 215, asks for the kth largest value in an unsorted array, counted by sorted order rather than by distinct values, and it's the problem quickselect gets asked to solve most often in a real loop. Given [3, 2, 1, 5, 6, 4] and k = 2, sorting descending gives [6, 5, 4, 3, 2, 1], so the answer is 5, the second entry.
The find_kth_largest function from earlier solves this directly. Converting "kth largest" into an index first is the part candidates most often get wrong under pressure: the kth largest element sits at index len(nums) - k once the array is sorted ascending, not at index k - 1 the way a kth smallest search would. Walking through the example with k = 2 and six elements, the target index is 6 - 2 = 4, meaning the algorithm is really searching for whichever value ends up in position 4 once the array is partitioned around enough pivots to place it there.
Tracing one partition pass makes the shrinking concrete. Say the random pivot lands on the value 4, at index 5. Partitioning moves everything smaller than 4 (three of the six values: 3, 2, 1) to the front and everything larger (5, 6) after it, so 4 settles into index 3. Since the target index 4 is greater than the pivot's landing index 3, the next call only searches indices 4 and 5, the two largest values, and finds the second-largest of those in one more pass. Two partition passes solve a six-element array; a full sort would have needed to place all six elements, not just the two that mattered.
Interviewers sometimes ask for the kth largest of a stream that keeps growing, rather than a fixed array handed to you up front. That's a different problem shape, since quickselect needs the whole array present to partition it, and a min-heap of size k, which only needs to see each new element once, becomes the better fit. Recognizing which of the two problems you're actually looking at, a fixed array versus a growing stream, is worth stating out loud before writing either solution.
Quickselect vs. Heap vs. Sorting: Which Should You Use in an Interview?
Reach for quickselect when the array is fully available up front and you need a single order-statistic answer, reach for a min-heap of size k when the data arrives as a stream or when k is small relative to n, and reach for a full sort only when the interviewer explicitly wants the whole ordering, not just one position in it.
The complexity numbers above lay out the gap directly, but the practical decision usually comes down to two questions rather than the numbers alone. First, do you need just one answer, like the kth largest value, or do you need k answers, like the k largest values as a group? Quickselect naturally returns a single value; getting all k largest values out of it takes one more step (everything on the correct side of the final partition), while a heap of size k already holds exactly that set once the pass finishes. Second, is the full input sitting in memory as an array, or arriving one element at a time? A heap handles a stream directly, discarding the smallest tracked element as new ones arrive; quickselect assumes the whole array is present to partition, so it doesn't apply cleanly to a stream at all.
Our guide to heap interview questions covers the min-heap side of this trade-off in full, including a working implementation of the k-closest-points pattern that generalizes directly to k-largest and k-smallest problems. Reading both pieces together covers the two patterns interviewers reach for most often when a question narrows down to "give me part of a sorted order, not all of it."
Full sorting is rarely the fastest choice once quickselect or a heap is on the table, but it's still the right answer when the interviewer wants the k largest values back in sorted order rather than any order, since both alternatives need an extra sort step at the end to satisfy that anyway.
What Should You Say to the Interviewer While You Solve It?
Say the target index out loud before you write a single line: "kth largest at index len(nums) minus k, once the array is sorted ascending" tells the interviewer you converted the English description into an index correctly, which is the single most common place candidates slip on this problem. Naming that conversion before coding turns a silent risk into a visible, correct step.
Once the partition function is written, narrate what each pass eliminates rather than only what it keeps: "the pivot landed at index 3, and since I need index 4, I can throw away everything at index 3 and below" shows the interviewer you understand why the algorithm is fast, not just that you memorized its shape. That sentence is doing the same job the complexity table does earlier in this piece, connecting a concrete step in the code to the reason it saves time over a full sort.
When you choose a random pivot instead of always taking the first or last element, say why before moving on: "I'm picking the pivot randomly so a sorted or reverse-sorted input can't force the worst case every time." An interviewer who sees random.randint appear without comment may read it as a copied detail rather than a deliberate choice, and stating the reason removes that doubt in one sentence. If asked what happens in the worst case despite the randomization, answer directly: O(n²) time, since an unlucky pivot on every pass shrinks the search space by only one element instead of by half, and that answer, given confidently, tends to satisfy the follow-up rather than inviting more of them.
Where Else Does Quickselect Show Up in Interviews?
Kth Largest Element in an Array is the problem quickselect solves most often, but the same partition-and-narrow idea answers a handful of related prompts once the base pattern is automatic. Finding the median of an unsorted array is quickselect with k fixed at the middle index (or an average of two middle indices for an even-length array), and "k closest points to origin" swaps the comparison key from raw value to squared distance from the origin but keeps the same partition logic underneath. Top K Frequent Elements applies the identical idea to a frequency count instead of the raw values, partitioning on frequency to isolate the k most common entries without sorting the full frequency table.
Our curated question bank pulls these variations from real onsite reports instead of an unfiltered public archive, so the version you practice matches what a current loop is actually asking rather than a phrasing that stopped showing up years ago. Pairing this with pattern recognition across the rest of the coding round turns quickselect into one identifiable shape among several, the moment "kth largest" or "without fully sorting" appears in a prompt, instead of a technique you only remember once someone points it out. And since every complexity claim in this piece rests on the same big-O reasoning that applies across every other pattern, our guide to time complexity in interviews is worth reading alongside this one if the O(n) versus O(n log n) gap here needed a second pass to click.
Practice Quickselect Until the Partition Step Is Automatic
The fastest way to make quickselect click is to trace the partition step by hand on a small array, five or six elements, before trusting the code to do it silently. Pick a pivot, move the smaller values to one side, watch where the pivot lands, and check that against the index you're searching for. Once that motion feels obvious on paper, the Python implementation above stops being something to memorize and becomes something you can rebuild from the partition logic alone, which is what an interviewer is actually checking for when they ask you to solve this from scratch.
Frequently Asked Questions
What is quickselect used for in coding interviews?
Quickselect finds a single order-statistic value, most often the kth largest or kth smallest element in an unsorted array, in O(n) average time instead of the O(n log n) a full sort would need. It shows up whenever a problem only needs one position in the sorted order rather than the entire sorted array.
Is quickselect faster than sorting?
On average, yes, quickselect runs in O(n) average time against O(n log n) for a full sort, since it only partitions the side of the array that can still contain the target index instead of placing every element in its final position. In the worst case, an unlucky pivot on every pass can degrade quickselect to O(n²), which is slower than sorting, so a randomized pivot is what keeps the average case the realistic outcome.
What is the worst case time complexity of quickselect?
O(n²), which happens when the pivot choice is unlucky on every single partition pass, most commonly when a fixed pivot rule (always the first or last element) meets a sorted or reverse-sorted input. Choosing the pivot randomly makes that worst case astronomically unlikely on real data, even though it remains possible in theory.
How is quickselect different from quicksort?
Quicksort recurses into both sides of every partition, since it needs the entire array sorted, which costs O(n log n) on average. Quickselect recurses into only the side that contains the target index and discards the other side entirely, which is the one change that drops its average running time to O(n).
Should I use quickselect or a heap for a kth largest problem?
Use quickselect when the full array is already available in memory and you need one answer. Use a min-heap of size k when the data arrives as a stream, when k is small relative to the array size, or when the input order needs to stay untouched, since quickselect partitions the array in place and a heap does not.
Does quickselect work on a stream of data?
Not directly, since quickselect needs the whole array present up front to partition it, so it doesn't apply cleanly to data arriving one element at a time. A min-heap of size k, which processes each new element as it arrives and only keeps the k most relevant ones, is the standard choice for that version of the problem.