Frontend Beauty
ESC

Type to search the knowledge base.

Find Median from Data Stream

Running median with two heaps — max-heap lows + min-heap highs, balance rules, and JS heap sketch.

advanced3 min read
  • dsa
  • heap
  • interview
  • Google
  • Meta
  • Amazon

The problem

Design a structure:

  • addNum(num)
  • findMedian() — median of all numbers so far

If even count, average of two middle values (float ok).

add 1, add 2 → median 1.5
add 3 → median 2

Brute

Keep a sorted array; binary insert O(n). Median O(1). Fine for small streams.

class MedianFinderBrute {
  private a: number[] = [];
  addNum(num: number): void {
    let i = 0;
    while (i < this.a.length && this.a[i] < num) i++;
    this.a.splice(i, 0, num);
  }
  findMedian(): number {
    const n = this.a.length;
    const m = n >> 1;
    return n % 2 ? this.a[m] : (this.a[m - 1] + this.a[m]) / 2;
  }
}

| add | O(n) | | median | O(1) |

Optimal: two heaps

  • lo: max-heap of lower half
  • hi: min-heap of upper half

Invariants:

  1. Every value in lo ≤ every value in hi
  2. sizes differ by at most 1

Median: if sizes equal → average of tops; else top of the larger half.

JS has no built-in heap — use a simple binary heap class in interviews.

class Heap {
  private data: number[] = [];
  constructor(private cmp: (a: number, b: number) => boolean) {} // true if a should be above b
  get size() {
    return this.data.length;
  }
  peek(): number {
    return this.data[0];
  }
  push(x: number) {
    this.data.push(x);
    this.up(this.data.length - 1);
  }
  pop(): number {
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length) {
      this.data[0] = last;
      this.down(0);
    }
    return top;
  }
  private up(i: number) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.cmp(this.data[i], this.data[p])) break;
      [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
      i = p;
    }
  }
  private down(i: number) {
    const n = this.data.length;
    while (true) {
      let best = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < n && this.cmp(this.data[l], this.data[best])) best = l;
      if (r < n && this.cmp(this.data[r], this.data[best])) best = r;
      if (best === i) break;
      [this.data[i], this.data[best]] = [this.data[best], this.data[i]];
      i = best;
    }
  }
}

class MedianFinder {
  private lo = new Heap((a, b) => a > b); // max-heap
  private hi = new Heap((a, b) => a < b); // min-heap

  addNum(num: number): void {
    if (!this.lo.size || num <= this.lo.peek()) this.lo.push(num);
    else this.hi.push(num);

    // rebalance
    if (this.lo.size > this.hi.size + 1) this.hi.push(this.lo.pop());
    else if (this.hi.size > this.lo.size) this.lo.push(this.hi.pop());
  }

  findMedian(): number {
    if (this.lo.size > this.hi.size) return this.lo.peek();
    return (this.lo.peek() + this.hi.peek()) / 2;
  }
}
addNum O(log n)
findMedian O(1)
space O(n)

Balance rules (say out loud)

After insert into the natural side, if lo has 2+ more than hi, move max of lo to hi. If hi is larger, move min of hi to lo. Prefer lo as the larger half for odd counts.

Edge cases

  • Single element
  • All equal
  • Decreasing stream
  • Even/odd switching

Common mistakes

  • Forgetting rebalance
  • Min/max heap swapped
  • Integer division for even median

Interview delivery

  1. Stream median → two heaps.
  2. Invariants.
  3. Implement or sketch heap.
  4. Trace 1,2,3.
  5. O(log n) add.

Further reading