TechPrep
Searching and orderingReadLabPracticeCheck

Heaps and top-K

A size-K min-heap keeps the K largest items seen so far; its top is the answer and everything smaller is discarded.

Kth Largest Element in an Array. Return the k-th largest element of nums (in sorted order, not the k-th distinct).

Signals that point here

The idea

Keep a min-heap of at most k items. Any item smaller than the heap's top cannot be among the k largest, so when the heap grows past k, pop the minimum.

In an interview, name the alternatives: sorting is O(n log n); quickselect is O(n) on average but O(n²) worst case and mutates the array; the heap is O(n log k) and works on a stream. Pick based on k, memory and whether data arrives online.

import heapq

def kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []             # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)      # drop the smallest
    return heap[0]

Complexity

O(n log k) time, O(k) space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: kth_largest([3, 2, 1, 5, 6, 4], 2)

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the k most frequent words, ties broken alphabetically.
  2. Merge k sorted linked lists into one sorted list.
  3. Design a structure that returns the median after each inserted number.

Check yourself

Why a min-heap for the largest K?

The top is the weakest of the current top K, so it is the one to evict when something larger arrives.

When is quickselect the better answer?

Offline data, average-case O(n) is acceptable, and mutating the array is allowed.

Saved in this browser.