Kth Largest Element in an Array

Kth Largest Element asks for the kth biggest number in an unsorted array. The clean interview answer is a min-heap of size k — a tiny priority queue that quietly keeps only the k largest numbers around.

The slow way first

The obvious idea: sort the array descending and return index k - 1. That works and is easy to write, but sorting is O(n log n) and throws away the fact that we only care about k numbers, not all n.

The question to ask: do I really need the whole array in order? No — I only need to track the k largest numbers as they go by, and among those the smallest one is the answer.

The idea: a min-heap of size k

Keep a min-heap (a priority queue whose smallest element is always on top). Walk the array and push every number. Whenever the heap grows past size k, pop the smallest — it cannot possibly be one of the k largest. After the scan, the heap holds exactly the k largest numbers, and its root (the minimum of those) is the kth largest.

The key insight: the heap never holds more than k items, so a push/pop costs O(log k), not O(log n). The root is the k-th largest because everything below the top k has already been popped away.

Walk through it

Step through the animation. The pointer num scans the input left to right; the strip below is the heap (drawn smallest-on-the-left so the root is visible). Watch size 3 appear after pushing 1, 5, 6, and 4 — each time we immediately pop the root to shrink back to k = 2. When the scan ends the heap is [5, 6], so the root 5 is the answer.

Pseudocode

make an empty min-heap
for each num in nums:
    push num onto the heap
    if the heap now has more than k items:
        pop the smallest (the root)
return the heap's root          # smallest of the k largest = kth largest

The Python solution

import heapq
 
def find_kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

• Python's heapq is a min-heap: heap[0] is always the smallest element.
• heappush adds a number; heappop removes and returns the smallest — both O(log k) since the heap stays at size k.
• The if len(heap) > k guard is the whole trick: we let the heap grow by one, then drop the smallest, so only the k largest survive.
• After the loop, heap[0] is the smallest of the k largest — exactly the kth largest.

Complexity

The heap uses only O(k) extra space. For small k this beats sorting handily. If you need the absolute fastest average case, quickselect finds the kth largest in O(n) on average by partitioning around a pivot — but it degrades to O(n²) in the worst case, so the heap is the safer interview default.

When this pattern shows up

Practice