Find the kth largest element in an unsorted array without fully sorting it.

How to think about it

The phrase the interviewer is fishing for is “I don’t need to sort the whole thing.” Sorting and indexing to k-1 works and is O(n log n), but it does far more than asked. The better instinct — and the one that scales to streaming data you can’t hold in memory — is a fixed-size min-heap that quietly throws away anything too small to be in the top-k.

Here is why a min-heap, which feels backwards at first. You want to keep the k largest values, and the value most at risk of being knocked out of that club is the smallest one currently in it — which is exactly what sits at the root of a min-heap. So stream the array through a heap capped at size k: push each element, and the instant the heap holds more than k, pop its minimum. Whatever survives to the end is the top-k, and the root — the smallest of those k — is the kth largest. Each element does at most one push and one pop on a heap of size k, so the whole thing is O(n log k).

A worked example

import heapq

def find_kth_largest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)   # evict the smallest; keep only the top-k
    return heap[0]                # smallest of the top-k = kth largest

print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))            # 2nd largest
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))   # duplicates are fine
print(find_kth_largest([1], 1))                           # single element
print(find_kth_largest([7, 6, 5, 4, 3], 5))               # k=n -> the minimum
print(find_kth_largest([3, 2, 1, 5, 6, 4], 1))            # k=1 -> the maximum

# Trace the size-k heap as elements stream through
def find_kth_largest_verbose(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        popped = None
        if len(heap) > k:
            popped = heapq.heappop(heap)
        note = f"pop {popped}" if popped is not None else "keep"
        print(f"  push {n}: heap={sorted(heap)} ({note})")
    return heap[0]

print("Trace for nums=[3,2,1,5,6,4], k=2:")
find_kth_largest_verbose([3, 2, 1, 5, 6, 4], 2)

5
4
1
3
6
Trace for nums=[3,2,1,5,6,4], k=2:
  push 3: heap=[3] (keep)
  push 2: heap=[2, 3] (keep)
  push 1: heap=[2, 3] (pop 1)
  push 5: heap=[3, 5] (pop 2)
  push 6: heap=[5, 6] (pop 3)
  push 4: heap=[5, 6] (pop 4)

The trace shows the heap acting as a bouncer for a two-seat club. The 1 never gets in; the 5 and 6 shove out the older, smaller 2 and 3; and the late 4 is itself too small and bounces straight back out. What remains is [5, 6] — the two largest — and the root 5 is the 2nd largest, the answer. (The trace prints sorted(heap) only so the internal array reads cleanly; the heap’s own layout is not sorted, just heap-ordered.)