Find Median from Data Stream

hardTests passed 2026-11-11v1.0.0

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

1. Core Invariant / The Trick

Maintain two balanced heaps: `lo` (max-heap of lower half) and `hi` (min-heap of upper half). Preserve two invariants on every `addNum`: (1) `max(lo) <= min(hi)`, and (2) `len(lo) >= len(hi)` differing by at most 1. Cleanest 3-step push: push into `lo`, pop `max(lo)` to `hi`, and if `len(hi) > len(lo)` pop `min(hi)` back to `lo`.

2. Complexity Bounds & Proof

Three-step push guarantees ordering and size invariants without conditional branches on comparison; `findMedian` is O(1).

3. Minimal Idiomatic Code

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap via negation
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0

4. Failure Modes & Interview Follow-ups

Pitfalls:- Comparing new value directly against heap tops creates fragile branching. - Integer division `(lo[0] + hi[0]) / 2` in C++/Java without `.0` / `2.0` truncates `.5`.

Follow-ups:- If all numbers are in `[0, 100]`, use a 101-bucket counting array for O(1) `findMedian`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Kth Largest Element in a Stream (O(N log k))

Browser Scratchpad

class MedianFinder {
  private lo = []; // max-heap
  private hi = []; // min-heap
  private push(h, v, cmp: (a, b) => boolean) {
    h.push(v);
    for (let i = h.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (cmp(h[p], h[i])) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }
  private pop(h, cmp: (a, b) => boolean) {
    const top = h[0], last = h.pop()!;
    if (h.length) {
      h[0] = last;
      for (let i = 0; ; ) {
        let b = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && cmp(h[l], h[b])) b = l;
        if (r < h.length && cmp(h[r], h[b])) b = r;
        if (b === i) break;
        [h[i], h[b]] = [h[b], h[i]];
        i = b;
      }
    }
    return top;
  }
  addNum(num): void {
    const maxC = (a, b) => a >= b;
    const minC = (a, b) => a <= b;
    this.push(this.lo, num, maxC);
    this.push(this.hi, this.pop(this.lo, maxC), minC);
    if (this.hi.length > this.lo.length) this.push(this.lo, this.pop(this.hi, minC), maxC);
  }
  findMedian() {
    return this.lo.length > this.hi.length ? this.lo[0] : (this.lo[0] + this.hi[0]) / 2;
  }
}

console.log("Loaded Find Median from Data Stream");

Console Output

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