Kth Largest Element in a Stream

easyTests passed 2026-11-11v1.0.0

TC: O(N log k)|SC: O(k)

1. Core Invariant / The Trick

Maintain a **min-heap** capped at size `k`: elements smaller than the k-th largest are evicted on `heappop`. The root `heap[0]` is always the k-th largest element.

2. Complexity Bounds & Proof

Heapifying N initial items and trimming to k takes O(N log k); every subsequent `add(val)` takes O(log k).

3. Minimal Idiomatic Code

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.h = list(nums)
        heapq.heapify(self.h)
        while len(self.h) > k:
            heapq.heappop(self.h)

    def add(self, val: int) -> int:
        if len(self.h) < self.k:
            heapq.heappush(self.h, val)
        elif val > self.h[0]:
            heapq.heapreplace(self.h, val)
        return self.h[0]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Using a max-heap requires storing all N seen elements and scanning k pops per query. - Calling `add` when heap size is still `k - 1` must push first before reading `heap[0]`.

Follow-ups:- Offline static array: Quickselect finds the k-th largest in O(N) expected time without extra memory.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

K Closest Points to Origin (O(N log k))Find Median from Data Stream (O(log N))

Browser Scratchpad

class KthLargest {
  private k;
  private h = [];
  constructor(k, nums) {
    this.k = k;
    for (const x of nums) this.add(x);
  }
  private push(val): void {
    this.h.push(val);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  private pop() {
    const top = this.h[0];
    const last = this.h.pop()!;
    if (this.h.length > 0) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
        i = s;
      }
    }
    return top;
  }
  add(val) {
    if (this.h.length < this.k) this.push(val);
    else if (val > this.h[0]) { this.pop(); this.push(val); }
    return this.h[0];
  }
}

console.log("Loaded Kth Largest Element in a Stream");

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.