Coding Interview: Use Quickselect to Find the K-th Largest Element with Duplicates

Prompt and scope

Given an unsorted integer array nums and 1 ≤ k ≤ nums.length, return the k-th element in non-increasing order. Duplicates occupy separate positions: the second largest value in [5, 5, 4] is 5, not the second distinct value. Target average time is O(n) with O(1) extra space when mutating the array is allowed; state that assumption before coding.

What the interviewer is testing

A strong answer maps “k-th largest” to the ascending index target = n-k, then explains that partition only needs to establish a boundary around the pivot; the other side never needs to be sorted. It handles duplicates, k=1, k=n, ordered inputs, and the difference between randomized average complexity and a worst-case guarantee.

Clarifications before coding

1. May the input be modified? In-place partition is O(1) extra space; preserving it requires an O(n) copy.
2. Is this the k-th position or the k-th distinct value? Position counting is the usual statement; distinct selection needs different duplicate handling.
3. Is data arriving as a stream? Quickselect is for one materialized array; a size-k min-heap gives O(n log k) processing for a stream.
4. Is a deterministic worst-case bound mandatory? Randomized Quickselect is average O(n); median-of-medians or a library guarantee is needed for a strict worst-case claim.

Recommended solution and derivation

Use three-way partitioning into values below, equal to, and above the pivot. For the converted ascending index target, continue with the left interval when the target lies left of lt, the right interval when it lies right of gt, and return the pivot when it lies in [lt, gt]. The equal band makes an all-equal input finish in one scan instead of repeatedly discarding one item.

import random

def kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k
    left, right = 0, len(nums) - 1
    while left <= right:
        pivot = nums[random.randint(left, right)]
        lt, i, gt = left, left, right
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot
    raise RuntimeError("unreachable")

Each iteration scans its current interval once. If the pivot shrinks the interval by a constant fraction, T(n)=T(cn)+O(n) yields average O(n); repeatedly selecting an extreme still gives O(n²) in the worst case. The iterative form avoids recursion depth and uses O(1) extra space.

Alternatives and trade-offs

Full sorting is easiest to verify, costs O(n log n), and is sensible when the array is small or a complete order is needed later. A size-k min-heap preserves the input and costs O(n log k) time and O(k) space, which fits streams or when k is much smaller than n. C++ std::nth_element exposes the same partition semantics with average-linear complexity; it does not sort either side of the selected position.

Failure modes, boundaries, and counterexamples

• Writing target = k-1 finds the k-th smallest value, reversing the requested order.
• A two-way partition that discards only one equal item can take O(n²) on [7, 7, 7, ...]; three-way partition consumes the equal band at once.
• Always choosing the last element can degrade on sorted and reverse-sorted inputs. Randomization lowers the likelihood, not the asymptotic worst-case bound.
• “k-th distinct largest” cannot reuse the stop condition without counting or removing the equal band.
• Reject an empty array, k=0, or k>n at the boundary instead of allowing an index error to hide an invalid prompt.

Tests and verification checklist

Compare randomized cases with sorted(nums)[-k]; include all-equal values, negatives and duplicates, k=1, k=n, sorted input, and reverse-sorted input. When mutation is allowed, assert the result rather than full array order. Fix the random seed for reproducibility and record comparison counts as n grows; one lucky run is not a complexity proof.

Follow-up questions

How can the worst case be guaranteed linear?

Choose a median-of-medians pivot so every round removes a fixed fraction, giving O(n) worst-case time. Its constants are higher, so production code commonly chooses randomized selection or a standard-library implementation.

How do you change it to the k-th smallest?

Use target = k-1 while keeping the ascending partition. Keeping the largest formulation as target=n-k is often clearer than reversing the array.

How do you support inserts and many rank queries?

One-shot Quickselect rescans on every query. For one fixed k, maintain a size-k min-heap; for arbitrary rank queries, consider a balanced tree augmented with subtree sizes and choose based on the update-to-query ratio.