4.17.1 — Kth Largest Element in a Stream

LeetCode 703 · Easy

The problem

Build a class that reports the k-th largest value seen so far. Values arrive one at a time through add(val), and every call returns the current answer.

KthLargest(3, [4, 5, 8, 2])
add(3)   →  4
add(5)   →  5
add(10)  →  5
add(9)   →  8
add(4)   →  8

Note this is the k-th largest value including duplicates, not the k-th distinct value.

The pattern

Keeping every value and sorting on each call is O(n \log n) per call. Far too much.

The observation that fixes it:

You only ever need the k largest values. Everything else can be thrown away permanently.

If a value is not in the top k now, it never will be, because more values only push it further down.

So keep exactly k values, and the answer is the smallest of them. A min-heap of size k gives that smallest at the root in O(1), and lets you replace it in O(\log k).

Min-heap for the k largest. People get this backwards, so hold onto the reason: the root must be the item you are about to evict, and that is the weakest of the ones you are keeping. A max-heap would put the strongest at the root — the item you never touch.

The solution

Python

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums[:]
        heapq.heapify(self.heap)                 # O(n), not O(n log n)
        while len(self.heap) > k:
            heapq.heappop(self.heap)             # drop everything below the top k

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]                      # the smallest of the k largest

TypeScript

// assumes a MinHeap with push, pop, peek, size
class KthLargest {
  private heap = new MinHeap<number>();
  constructor(private k: number, nums: number[]) {
    for (const n of nums) {
      this.heap.push(n);
      if (this.heap.size > k) this.heap.pop();
    }
  }

  add(val: number): number {
    this.heap.push(val);
    if (this.heap.size > this.k) this.heap.pop();
    return this.heap.peek()!;
  }
}

heap[0] is the answer, and it is O(1). The heap holds the k largest values, and its root is the smallest of them — which is precisely the k-th largest overall.

heapify is O(n), not O(n \log n). Building a heap in place by sifting down from the middle is cheaper than pushing n items one at a time. The derivation is in 4.16, and knowing this is a small, reliable way to sound like you understand the structure rather than the API.

Push then trim, rather than compare then push. You could check val > heap[0] first and skip the push when it is smaller. That saves a little work but adds a branch and an edge case when the heap is not yet full. Push-then-trim is one shape with no special case.

Complexity

add is O(\log k). Construction is O(n + (n - k)\log n).

Space is O(k) — and that is the point. The stream can be infinite and memory stays flat.

Why not sort, and why not a full heap

Sorting on every call is O(n \log n) per call and stores everything.

A heap of all n elements is O(\log n) per push but O(n) space, and getting the k-th largest would mean popping k times and putting them back.

A size-k heap is O(\log k) per call and O(k) space, and the answer is always sitting at the root. Since k is usually much smaller than n, this is better on both counts.

The general principle: discard what can never be part of the answer, as early as you can. It is the same instinct as the run-start guard in 4.4.9 and the eviction rule in a monotonic stack.

Where this goes next

• Top K Frequent Elements — the same size-k heap over counts. 4.4.5.
• K Closest Points to Origin — size-k heap over distances, but a max-heap this time, because you want the k smallest. 4.17.3.
• Find Median from Data Stream — two heaps facing each other. 4.17.7.
• Real systems — "top 10 slowest queries", "the 20 largest files", "the 100 most active users". All the same size-k heap, and all chosen because the data does not fit in memory.

What the interviewer will push on

"Min-heap or max-heap, and why?" Min-heap for the k largest — the root is the one you evict.

"Why not keep everything sorted?" O(n \log n) per call and unbounded memory.

"What if k is close to n?" The heap stops helping, since \log k approaches \log n and the memory saving disappears. Sorting once and maintaining the array becomes competitive.

"Why is heapify O(n)?" Sifting down from the middle: most nodes are near the bottom and have almost nothing to sift.

One thing to volunteer: say why a value outside the top k can be discarded forever. That sentence is the whole design.

Next: 4.17.2 Last Stone Weight — a simulation where the heap is the obvious tool.