Coding Interview: Find the Kth Largest Element in an Array

Prompt and Applicable Context

Given an integer array nums and an integer k, return the kth largest element in sorted order, not the kth distinct value. Assume 1 <= k <= nums.length <= 100,000 and -10,000 <= nums[i] <= 10,000.

For example, nums = [3, 2, 1, 5, 6, 4] and k = 2 returns 5. For nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4, the answer is 4: duplicate values occupy separate ranks.

This is a representative coding-interview order-statistics problem. A full sort, a size-k min-heap, and quickselect are all valid under different constraints. The main answer below uses randomized three-way quickselect because the input is an in-memory mutable array and only one rank is required. It mutates nums; copy the array first if the caller requires input preservation.

What the Interviewer Evaluates

The first signal is contract precision. “Kth largest” means position k in descending sorted order, including duplicates. It does not mean the kth distinct value, the largest k values, or index k in a zero-based array. In ascending order, the requested element has zero-based index n - k.

The second signal is whether the candidate derives alternatives instead of reciting quickselect. Sorting is the safest baseline at O(n log n). A size-k min-heap takes O(n log k) time and O(k) space and also works for streaming input. Quickselect discards the partition that cannot contain the target and has expected O(n) time, but randomized pivoting does not remove its O(n^2) worst case.

The third signal is a stated partition invariant. Code that “looks like quicksort” is not enough. The candidate should be able to say what is known about elements before lt, between lt and i, between i and gt, and after gt, then explain why the next search interval still contains the target rank.

Finally, the interviewer looks for duplicate handling, mutation disclosure, invalid-input behavior, iterative control to avoid recursion-depth risk, and tests that compare the result with a simple oracle. An optimized algorithm without a proof boundary or adversarial tests is incomplete.

Questions to Clarify Before Answering

• Does kth largest count duplicates? This answer follows sorted positions, so [5, 5, 4] with k = 2 returns 5. A distinct-rank requirement would need deduplication or frequency-aware selection.
• Is k guaranteed valid, and can the array be empty? The stated interview contract guarantees 1 <= k <= n. The implementation still raises ValueError outside that range so its standalone behavior is explicit.
• May the function mutate the input? In-place partitioning gives O(1) auxiliary space. If mutation is forbidden, copy first and accept O(n) additional space.
• Is the input fully available or streaming? Quickselect needs random access and mutation. For an unbounded stream, keep a size-k min-heap instead.
• Do we need one query or many rank queries on the same data? Quickselect is attractive for one rank. Sorting once can be better when many later queries justify the initial O(n log n) work.
• Is the value range genuinely small and fixed? The stated range has only 20,001 possible integer values, so counting is a valid alternative. It costs O(n + R) time and O(R) space for range width R, but should not be presented as a general solution when values are unbounded.
• Must worst-case time be bounded? Randomized quickselect gives expected linear time, not deterministic worst-case linear time. If a strict worst-case guarantee is required, discuss median-of-medians or choose a heap with predictable O(n log k) time.

30-Second Answer Framework

“The kth largest element is the item at ascending index n - k, with duplicates counted. Sorting gives a simple O(n log n) baseline, and a size-k min-heap gives O(n log k) time for streaming or non-mutating input. Because this problem asks for one rank in a mutable in-memory array, I would use iterative randomized quickselect. I partition the active interval into values smaller than, equal to, and greater than a random pivot. If n - k lies in the equal band, the pivot is the answer; otherwise I keep only the side containing that index. Three-way partitioning avoids repeatedly peeling off equal values. Expected time is O(n), worst case O(n^2), and auxiliary space is O(1). I would verify it against sorting on random arrays plus all-equal, sorted, reverse-sorted, duplicate-heavy, and boundary-k cases.”

Step-by-Step Deep Answer

Start with an oracle. Sorting ascending and returning sorted(nums)[len(nums) - k] is easy to explain and hard to get wrong. It establishes the rank conversion and provides a reference result for testing. Its cost is O(n log n) time and O(n) space when preserving the original input with a copy.

A bounded heap improves the work when k is small or data arrives incrementally. Push each value into a min-heap and remove the minimum whenever its size exceeds k. After all values, the root is the smallest among the largest k elements, hence the kth largest. The heap stores k values, so the cost is O(n log k) time and O(k) space. If k is close to n and the whole array is already available, this advantage shrinks.

Quickselect uses the fact that only one final position matters. Convert the descending rank to target = len(nums) - k. In each active interval [left, right], choose a random pivot value and perform a Dutch-national-flag partition. During the scan, maintain:

• [left, lt) contains values smaller than the pivot.
• [lt, i) contains values equal to the pivot.
• [i, gt] is unclassified.
• (gt, right] contains values greater than the pivot.

When the scan ends, [lt, gt] is the complete equal band. If target < lt, continue in the smaller-value side. If target > gt, continue in the greater-value side. Otherwise the target falls inside the equal band, so the pivot value is the answer. This treatment matters for arrays such as [7, 7, 7, 7]: a two-way partition can repeatedly produce almost unchanged work, while the three-way version finishes after one scan.

import random


def find_kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    target = len(nums) - k
    left = 0
    right = len(nums) - 1

    while left <= right:
        pivot = nums[random.randrange(left, right + 1)]
        lt = left
        i = left
        gt = 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 for a valid k")

The i increment is intentionally asymmetric. After swapping a value greater than the pivot with nums[gt], the incoming value at i has not been classified, so i stays in place. After moving a smaller value left, both swapped positions have known classifications, so both lt and i advance.

Correctness follows from the invariant and rank elimination. The partition preserves every input element and ends with all smaller values before the equal band and all greater values after it. Therefore every index in [lt, gt] has the pivot value in sorted order. If the target is outside that band, the discarded side and equal band contain no element that can occupy the target index; the retained interval still contains it. Each iteration either returns or strictly shortens the interval, so a valid target is eventually returned.

Each partition scans the current interval once. With random pivots, the expected total work over successively retained intervals is O(n). A sequence of consistently extreme pivots can leave intervals of sizes n - 1, n - 2, and so on, producing O(n^2) worst-case time. The implementation is iterative and partitions in place, so its auxiliary space is O(1). Random-number-generator state and the input array itself are not counted as auxiliary storage.

Test with a simple sorted oracle rather than only fixed examples:

def oracle(nums: list[int], k: int) -> int:
    return sorted(nums)[len(nums) - k]


cases = [
    ([3, 2, 1, 5, 6, 4], 2),
    ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
    ([1], 1),
    ([7, 7, 7, 7], 3),
    ([-5, -1, -3, -1], 2),
    (list(range(1000)), 1),
    (list(range(1000)), 1000),
]

for values, rank in cases:
    assert find_kth_largest(values.copy(), rank) == oracle(values, rank)

Add generated arrays with many duplicate values and compare every valid k with the oracle. Also assert that k = 0, k > n, and an empty array raise the documented error. Seeding the random generator makes a failing property test reproducible; running multiple seeds exercises different partition paths.

High-Quality Sample Answer

“I’ll treat duplicates as separate sorted positions and assume k is valid. If the array were sorted ascending, the answer would be at index n - k. My baseline is to sort and index, which is O(n log n). A size-k min-heap is O(n log k) and would be my choice for streaming data.

Here we have one query and may mutate the array, so I’ll use randomized quickselect. Within the active range, I choose a random pivot and split values into less than, equal to, and greater than the pivot. The three-way split is important because duplicates should occupy several ranks and an all-equal input should finish in one partition. After partitioning, if n - k is inside the equal range, I return the pivot. Otherwise I discard the side that cannot contain that index and repeat iteratively.

The invariant is that everything before lt is smaller, everything from lt to i is equal, everything after gt is greater, and the middle unknown section is still unclassified. This proves the final equal band has its correct sorted rank interval. The retained side therefore still contains the answer.

The expected runtime is O(n) because a random pivot usually removes a substantial portion, though the worst case remains O(n^2). The loop and in-place partition use O(1) auxiliary space. I would disclose that the function mutates its input, compare it with a sorting oracle on generated arrays, and include duplicates, all-equal data, sorted and reverse-sorted arrays, negative values, k = 1, and k = n.”

Common Mistakes

• Return the kth distinct value → duplicates are separate positions in the contract → Convert directly to ascending index n - k without deduplicating.
• Use index k or k - 1 in ascending order → the direction conversion is wrong → Check k = 1 maps to n - 1 and k = n maps to 0.
• Claim a min-heap solution is O(n log n) → the heap never exceeds k elements → State O(n log k) time and O(k) space.
• Recurse into both partitions → that performs quicksort work and ignores the single-rank goal → Continue only in the interval containing target.
• Always choose the first or last pivot → sorted or crafted input can repeatedly create size-n - 1 intervals → Randomize the pivot and retain the worst-case caveat.
• Use a two-way partition without discussing duplicates → equal-heavy arrays can make poor progress → Create one equal band and return when the target falls inside it.
• Increment i after swapping with gt → the incoming value remains unclassified and may be skipped → Keep i fixed until that value is classified.
• Claim randomization guarantees linear time → unlucky pivots still exist → Say expected O(n), worst-case O(n^2).
• Hide input mutation → callers may depend on the original order → State the mutation contract or copy and account for O(n) space.
• Test only two examples → off-by-one, duplicates, and partition bugs remain invisible → Compare against sorting across boundaries, structured cases, and generated inputs.

Follow-Up Questions and How to Handle Them

Follow-up 1: What changes if the input is an unbounded stream?

Quickselect no longer fits because the complete random-access array does not exist. Maintain a min-heap of at most k values. Push until it reaches k; afterward replace the root only when a larger value arrives. The root is the kth largest value seen so far. Updates cost O(log k), queries cost O(1), and memory is O(k). If k itself changes arbitrarily, this state may be insufficient and the contract needs a richer ordered structure or retained data.

Follow-up 2: What if the function must preserve the input?

The simplest adaptation is working = nums.copy() and quickselect on working, changing auxiliary space to O(n). A size-k heap preserves input with O(k) space and may be better when k is small. Full sorting of a copy is simpler when n is modest or many rank queries will reuse the sorted result.

Follow-up 3: Can you guarantee worst-case linear time?

Median-of-medians chooses a pivot that discards a constant fraction in the worst case, giving deterministic O(n) selection. Its implementation and constants are larger, so randomized quickselect is often the practical interview choice unless the requirement explicitly demands a worst-case bound. A bounded heap offers a simpler predictable O(n log k) alternative.

Follow-up 4: How would you use the small integer range?

Create a frequency array for values from -10,000 through 10,000, scan nums, then walk frequencies from high to low while subtracting counts from k. The first bucket that contains the remaining rank is the answer. With range width R = 20,001, this costs O(n + R) time and O(R) space. It is deterministic and handles duplicates naturally, but it becomes unsuitable when the range is large or unbounded.

Follow-up 5: What if the interviewer asks for the largest k elements, sorted?

One order statistic is no longer the full output. A size-k heap followed by sorting the heap costs O(n log k + k log k) time and O(k) space. Quickselect can partition around rank n - k, after which sorting the selected k values costs expected O(n + k log k). Choose based on mutation, memory, worst-case requirements, and whether output order is required.

Follow-up 6: How do you make randomized test failures reproducible?

Accept an injected random-number generator or seed the generator before each test. Record the seed, input, and k on failure. Run the same input across several fixed seeds, and compare every answer with the sorting oracle. This separates an algorithm error from one particular pivot path while preserving repeatability in continuous integration.