Kth Largest Element in an Array

How you get there

1. 1A min-heap of size k keeps exactly the k largest seen so far.
2. 2Its root is the kth largest by construction.
3. 3Quickselect gives O(n) average if the interviewer pushes further.

Solution

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)   # one sift instead of push+pop
    return heap[0]

Time

O(n log k)

Space

O(k)

What goes wrong

Using a max-heap of everything is O(n log n) and defeats the point of bounding the heap at k.