6.3 Two Heaps

Demo: Find Median from Data Stream — LC 295 (Hard — Amazon/Google/Meta High)

Statement (Demo): Design MedianFinder with addNum(num) and findMedian(), which returns the median of every number added so far (the mean of the two middles for an even count). Example: addNum(1), addNum(2), findMedian()=1.5, addNum(3), findMedian()=2.0 | ⚡ at most 5×10⁴ calls

Approach: low is a max-heap of the smaller half, high a min-heap of the larger half. Push every number into low, move low's top to high (so every low ≤ every high), then move back if high got bigger. The median is low's top, or the mean of both tops. (MinHeap → 6.1; a max-heap is the same class with a reversed compare.)

class MedianFinder {
  constructor() {
    this.low = new MinHeap((a, b) => b - a); // max-heap: smaller half
    this.high = new MinHeap(); // min-heap: larger half
  }
  addNum(num) {
    this.low.push(num);
    this.high.push(this.low.pop()); // keep every low ≤ every high
    if (this.high.size > this.low.size) this.low.push(this.high.pop()); // low may hold one extra
  }
  findMedian() {
    return this.low.size > this.high.size
      ? this.low.peek()
      : (this.low.peek() + this.high.peek()) / 2;
  }
}

Complexity: addNum O(log n), findMedian O(1), Space O(n)