Kth Largest Element in an Array

This is the "hello world" of heaps. It is usually the first heap question in a screen, and the interviewer is testing two things: whether you pick the right heap, and whether you know when you don't need one.

The problem

Given an array of integers and a number k, return the value that would be at position k if the array were sorted from largest to smallest. Duplicates count as separate items: in [4, 4, 1], the 2nd largest is 4.

• numbers = [3, 2, 1, 5, 6, 4], k = 2 → 5. Sorted descending it is [6, 5, 4, 3, 2, 1], and position 2 is 5.
• numbers = [7, 7, 7], k = 3 → 7.

Constraints: 1 ≤ k ≤ n ≤ 10⁵, values between -10⁴ and 10⁴.

Clarifying questions

• Is it the k-th largest value, or the k-th largest distinct value? The k-th in sorted order, so duplicates count.
• Is k always valid? Yes, 1 ≤ k ≤ n.
• May I change the input array? Assume no; the heap approach does not need to.
• Is this a one-off query or a stream? One-off here, but the stream version is a common follow-up, so pick a solution that extends to it.

Approach 1: sort

Sort a copy from largest to smallest and read position k - 1.

1def kth_largest_sort(numbers: list[int], k: int) -> int:2    """Sort a copy from largest to smallest and index it."""3    ordered = sorted(numbers, reverse=True)4    return ordered[k - 1]

Time O(n log n), space O(n) for the sorted copy. At n = 10⁵ this runs in milliseconds, so it is not too slow for these limits. Say that honestly. What is wrong is the amount of work: it puts all n items in order when you only need to know one position. The interviewer's next line is almost always "can you do better than sorting?", and it breaks completely if numbers arrive one at a time.

The key insight

You never need the full order. You only need the k largest values, and among them, the smallest.

Imagine a club with k seats that only admits the biggest numbers. Numbers walk past one by one. While there is a free seat, anyone gets in. When the club is full, a newcomer is compared with the weakest member — the smallest number inside. If the newcomer is bigger, the weakest member is thrown out and the newcomer takes the seat. Otherwise the newcomer walks on.

After every number has walked past, the club holds exactly the k largest. And its weakest member is the k-th largest overall. Every number bigger than it is inside the club, and there are exactly k - 1 of them.

So the structure must answer one question fast: "who is the weakest member?" That is the minimum of the club, which is a min-heap. Its root is both the eviction candidate and, at the end, the answer.

Approach 2: a size-k min-heap

1. Put the first k numbers into a list and heapify it — O(k).
2. For each remaining number, compare it with the root.
3. If it is bigger, heapreplace: pop the root and push the new number in a single sift.
4. Otherwise skip it; it cannot be in the top k.
5. Return the root.

1import heapq23def kth_largest_heap(numbers: list[int], k: int) -> int:4    """Keep the k largest values seen so far in a min-heap; its root is the answer."""5    heap = numbers[:k]6    heapq.heapify(heap)                      # O(k)7    for value in numbers[k:]:8        if value > heap[0]:                  # beats the weakest of the k we keep9            heapq.heapreplace(heap, value)   # pop the root and push value, one sift10    return heap[0]

Dry run on [3, 2, 1, 5, 6, 4] with k = 2. After heapify, the heap is [2, 3].

Return 5. Correct.

Complexity. Time O(k + (n - k) log k), which is O(n log k): each value does at most one sift on a heap of size k. Space O(k). With k = 2 the heap never holds more than two numbers, however long the array is. Note the > rather than >=: a value equal to the root would replace an equal value and change nothing, so skipping it saves work.

Approach 3: quickselect

When the array is static and you want the best average time, quickselect finds position k without sorting. Pick a random pivot, split into "bigger", "equal" and "smaller", and recurse only into the part that holds position k.

1import random23def kth_largest_quickselect(numbers: list[int], k: int) -> int:4    """Quickselect with a random pivot and a three-way split."""5    candidates = numbers6    while True:7        pivot = random.choice(candidates)8        bigger = [v for v in candidates if v > pivot]9        equal = [v for v in candidates if v == pivot]10        if k <= len(bigger):11            candidates = bigger                      # answer is among the bigger12        elif k <= len(bigger) + len(equal):13            return pivot                             # answer is the pivot itself14        else:15            k -= len(bigger) + len(equal)16            candidates = [v for v in candidates if v < pivot]

Average time O(n): each round keeps about half, so the work is n + n/2 + n/4 + … ≈ 2n. Worst case O(n²) if the pivot is unlucky every time, which a random pivot makes very unlikely. This version uses O(n) extra space for the lists; the in-place Lomuto or Hoare partition brings it to O(1), and the Sort and Search section builds that version. The three-way split matters: with many equal values, a two-way split can loop without shrinking.

Which one to offer? Say both. "The heap is O(n log k), uses O(k) memory and works on a stream. Quickselect is O(n) on average but O(n²) in the worst case and needs the whole array in memory."

Edge cases

• k = 1: the heap holds one number and the answer is the maximum. k = n: the heap holds everything and the answer is the minimum. Both work unchanged.
• Duplicates such as [7, 7, 7], k = 3: the heap holds all three 7s. Duplicates count as separate items, which is what the problem wants.
• Negative numbers: nothing special; comparison works the same.
• A single element: numbers[:1] is the whole array, the loop does nothing, and the root is returned.

Follow-ups

• "Numbers arrive as a stream; return the k-th largest after each one." Keep the same size-k min-heap as a class field. Each add pushes, trims to k, and returns heap[0] in O(log k). Quickselect cannot do this.
• "Return the k-th smallest instead." Mirror everything: a size-k max-heap, built by negating values.
• "The data does not fit in memory." The heap needs only O(k) memory and reads the data once, so it streams from disk. Quickselect needs the whole array.