Kth Largest Element: Heap Versus Quickselect

"Kth Largest Element in an Array" shows up again and again in Meta, Amazon, LinkedIn phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Top-K and Heaps pattern quickly and code it cleanly. Part 1 of 11 in the Top-K and Heaps arc.

The Problem

Return the k-th largest element in an unsorted array (in sorted order, not distinct). One of the most-reported interview questions anywhere, because it has three legitimate solutions with different trade-offs — and the discussion is the interview.

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

K-th extreme without full sorting is the founding Top-K cue. Full sort costs O(n log n) and computes n − k answers nobody asked for; a size-k min-heap keeps exactly the k largest seen, with the k-th largest sitting at the root.

The Approach

Push each element; when the heap exceeds k, pop the minimum — evicting anything that provably is not among the k largest. After the pass, the root is the answer. O(n log k), O(k) space, and it works on streams.

Quickselect partitions like quicksort but recurses one side only: O(n) average, O(n²) worst (mitigated by random pivots). State the decision rule: heap for streaming or tiny k; quickselect for one-shot in-memory arrays; heapq.nlargest when someone just wants it done.

Python Solution

import heapq


def find_kth_largest(nums: list[int], k: int) -> int:
    """K-th largest via a bounded min-heap of size k. O(n log k)."""
    heap: list[int] = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)        # evict the smallest of the candidates
    return heap[0]

Complexity

• Time: O(n log k) — n pushes into a heap capped at k elements
• Space: O(k) — the bounded heap

Interview Tips and Follow-Ups

• Duplicates count — the 4th largest of [5, 5, 6, ...] treats each 5 separately. Confirm 'in sorted order, not distinct' before coding.
• Be ready to write quickselect, not just name it — Meta asks for it as the follow-up about half the time by candidate reports.
• heapify on the first k elements then push-pop the rest shaves constants; mentioning it shows you know heapify is O(k), not O(k log k).

That wraps part 1 of the Top-K and Heaps arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.