Quickselect Interview Pattern: Finding the Kth Element
"Find the kth largest element" is one of the most common interview prompts, and there are three good answers: sort, heap, or quickselect. Knowing all three and explaining when you'd choose each is what makes a strong answer. This guide focuses on the quickselect interview pattern: what it is, how to implement it without off-by-one bugs, and how to discuss its trade-offs.
Three options, one table
| Approach | Time | Extra space | Best when |
|---|---|---|---|
| Sort, then index | O(n log n) | O(1)–O(n) | Simplicity matters; n is small |
| Min-heap of size k | O(n log k) | O(k) | Streaming data, or k much smaller than n |
| Quickselect | O(n) average, O(n²) worst | O(1) iterative | One-off query on an in-memory array |
A great opening line: "The simplest answer is to sort, which is n log n. A heap gets n log k. Quickselect averages linear time, so I'll go with that unless you'd prefer the safer worst case."
That sentence shows you know the landscape and lets the interviewer steer.
The core idea
Quickselect borrows the partition step from quicksort:
- Pick a pivot.
- Partition the array so smaller elements are on one side and larger on the other.
- The pivot is now at its final sorted index
p. - If
pis the target index, you're done. Otherwise recurse (or loop) into only one side.
Because you only follow one side, the average work is n + n/2 + n/4 + ..., which sums to about 2n, so O(n).
Turn "kth largest" into an index
This is where most bugs start. For a zero-indexed array sorted ascending:
- kth smallest is at index
k - 1 - kth largest is at index
n - k
Say the conversion out loud before writing code. It prevents the most common off-by-one error.
A clean implementation (Python)
import random
def find_kth_largest(nums, k):
target = len(nums) - k
lo, hi = 0, len(nums) - 1
while True:
pivot_idx = random.randint(lo, hi)
nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
if store == target:
return nums[store]
if store < target:
lo = store + 1
else:
hi = store - 1
Narration for the interviewer: "I pick a random pivot to avoid the worst case on sorted input, move it to the end, partition with the Lomuto scheme, and then shrink the search range to the side that contains my target index."
Why the random pivot matters
If you always pick the last element and the input is already sorted, each partition removes only one element, giving O(n²). A random pivot makes that worst case extremely unlikely. Mentioning this unprompted is a strong signal.
If the interviewer pushes on guaranteed linear time, you can mention median-of-medians as a deterministic O(n) pivot strategy. You usually don't need to implement it; naming it and explaining the trade-off (higher constant factors, more complex code) is enough.
Handling duplicates
Lomuto partitioning can degrade when many elements are equal, because equal values all land on one side. If the input may have many duplicates, mention a three-way partition (less than, equal to, greater than the pivot). When the target index falls inside the "equal" block, you can return immediately.
Common bugs
- Wrong target index. Mixing up
k - 1andn - k. - Off-by-one ranges. Using
hi = storeinstead ofstore - 1can loop forever. - Forgetting to move the pivot back after partitioning.
- Fixed pivot on sorted input. Leads to quadratic time.
- Mutating input silently. Quickselect reorders the array; ask if that's acceptable or copy first.
Variants you might be asked
- K closest points to the origin: quickselect on distance.
- Top K frequent elements: count first, then quickselect on frequencies (or bucket sort).
- Median of an unsorted array: quickselect for index
n // 2(andn // 2 - 1for even length). - Wiggle sort or partition-around-median problems that need the median first.
How to close the answer
Finish with complexity and a trade-off: "Average O(n) time, O(1) extra space since it's iterative, worst case O(n²) but unlikely with a random pivot. If this were a data stream, I'd switch to a heap of size k."
Practice the explanation, not just the code
Quickselect is short to write but easy to fumble under pressure, mostly at the index conversion and the loop bounds. If you want a structured way to rehearse the out-loud explanation before your interview, Luna Interview is built for practice and prep—never as a shortcut during a live round.
Checklist
- [ ] Can compare sort vs heap vs quickselect in one sentence each
- [ ] Converts kth largest to index
n - kout loud - [ ] Uses a random pivot and explains why
- [ ] Knows when to mention three-way partitioning
- [ ] States average and worst-case complexity
- [ ] Asks whether mutating the input is OK
Rehearse with an AI interview copilot, then browse commonly reported interview questions.