Quickselect Interview Pattern: Finding the Kth Element

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

ApproachTimeExtra spaceBest when
Sort, then indexO(n log n)O(1)–O(n)Simplicity matters; n is small
Min-heap of size kO(n log k)O(k)Streaming data, or k much smaller than n
QuickselectO(n) average, O(n²) worstO(1) iterativeOne-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:

  1. Pick a pivot.
  2. Partition the array so smaller elements are on one side and larger on the other.
  3. The pivot is now at its final sorted index p.
  4. If p is 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:

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

Variants you might be asked

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