Mental Model

We keep two groups of numbers: smaller half and larger half, so the middle number is easy to find.

Analogy: Imagine two boxes: one holds smaller numbers, the other holds bigger numbers. The middle number is at the edge between these boxes.

MaxHeap (smaller half): 5 -> 3 -> 1
MinHeap (larger half): 6 -> 8 -> 9
Median is between top of MaxHeap and MinHeap.

Dry Run Walkthrough

Input: Stream: 5, 2, 8, 3

Goal: Find the median after each number is added

Step 1: Add 5 to max heap (smaller half)

MaxHeap: [5]
MinHeap: []
Median: 5

Why: Start by putting first number in smaller half

Step 2: Add 2 to max heap, then balance by moving largest from max heap to min heap

MaxHeap: [2]
MinHeap: [5]
Median: (2 + 5) / 2 = 3.5

Why: Keep heaps balanced so median is average of tops

Step 3: Add 8 to min heap (larger half), then balance by moving smallest from min heap to max heap

MaxHeap: [5, 2]
MinHeap: [8]
Median: 5

Why: Max heap can have one extra element for odd count

Step 4: Add 3 to max heap, then balance by moving largest from max heap to min heap

MaxHeap: [3, 2]
MinHeap: [5, 8]
Median: (3 + 5) / 2 = 4

Why: Balance heaps to keep size difference at most one

Result:

MaxHeap: [3, 2]
MinHeap: [5, 8]
Median after last insertion: 4

Annotated Code

DSA Typescript

class Heap {
  data: number[] = [];
  comparator: (a: number, b: number) => boolean;

  constructor(comparator: (a: number, b: number) => boolean) {
    this.comparator = comparator;
  }

  size(): number {
    return this.data.length;
  }

  peek(): number | null {
    return this.data.length === 0 ? null : this.data[0];
  }

  push(val: number): void {
    this.data.push(val);
    this.bubbleUp();
  }

  pop(): number | null {
    if (this.data.length === 0) return null;
    const top = this.data[0];
    const end = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = end;
      this.bubbleDown();
    }
    return top;
  }

  bubbleUp(): void {
    let index = this.data.length - 1;
    const element = this.data[index];
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this.data[parentIndex];
      if (this.comparator(element, parent)) {
        this.data[index] = parent;
        index = parentIndex;
      } else {
        break;
      }
    }
    this.data[index] = element;
  }

  bubbleDown(): void {
    let index = 0;
    const length = this.data.length;
    const element = this.data[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = -1;

      if (leftChildIndex < length) {
        if (this.comparator(this.data[leftChildIndex], element)) {
          swapIndex = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        if (
          this.comparator(this.data[rightChildIndex],
          swapIndex === -1 ? element : this.data[leftChildIndex])
        ) {
          swapIndex = rightChildIndex;
        }
      }

      if (swapIndex === -1) break;

      this.data[index] = this.data[swapIndex];
      index = swapIndex;
    }
    this.data[index] = element;
  }
}

class MedianFinder {
  maxHeap: Heap; // smaller half
  minHeap: Heap; // larger half

  constructor() {
    this.maxHeap = new Heap((a, b) => a > b); // max heap
    this.minHeap = new Heap((a, b) => a < b); // min heap
  }

  addNum(num: number): void {
    if (this.maxHeap.size() === 0 || num <= this.maxHeap.peek()!) {
      this.maxHeap.push(num); // add to smaller half
    } else {
      this.minHeap.push(num); // add to larger half
    }

    // balance heaps sizes
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.push(this.maxHeap.pop()!); // move largest from smaller half to larger half
    } else if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.push(this.minHeap.pop()!); // move smallest from larger half to smaller half
    }
  }

  findMedian(): number | null {
    if (this.maxHeap.size() === 0 && this.minHeap.size() === 0) {
      return null; // no elements
    }
    if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.peek()!; // odd count, max heap top is median
    } else {
      return (this.maxHeap.peek()! + this.minHeap.peek()!) / 2; // even count, average of tops
    }
  }
}

// Driver code
const mf = new MedianFinder();
const stream = [5, 2, 8, 3];
for (const num of stream) {
  mf.addNum(num);
  console.log(mf.findMedian());
}

if (this.maxHeap.size() === 0 || num <= this.maxHeap.peek()!) {

decide which heap to add the new number to keep smaller half and larger half

if (this.maxHeap.size() > this.minHeap.size() + 1) {

balance heaps if smaller half has more than one extra element

else if (this.minHeap.size() > this.maxHeap.size()) {

balance heaps if larger half has more elements

if (this.maxHeap.size() > this.minHeap.size()) {

if odd count, median is top of smaller half

else { return (this.maxHeap.peek()! + this.minHeap.peek()!) / 2; }

if even count, median is average of tops of both heaps

OutputSuccess

5 3.5 5 4

Complexity Analysis

Time: O(log n) per insertion because each addNum operation pushes and pops from heaps which take O(log n)

Space: O(n) because all numbers are stored in the two heaps

vs Alternative: Compared to sorting the entire stream after each insertion (O(n log n)), using two heaps is much faster for continuous median queries.

Edge Cases

empty stream

findMedian returns null or error if called before any insertion

DSA Typescript

if (this.maxHeap.size() === 0 && this.minHeap.size() === 0) { return null; }

all numbers equal

heaps balance normally, median is that number

DSA Typescript

if (this.maxHeap.size() > this.minHeap.size() + 1) {

stream with negative and positive numbers

heaps correctly separate smaller and larger halves, median computed correctly

DSA Typescript

if (this.maxHeap.size() > this.minHeap.size()) {

When to Use This Pattern

When you need to find the median of a growing list of numbers efficiently, use two heaps to keep track of smaller and larger halves for quick median access.

Common Mistakes

Mistake: Not balancing the heaps after insertion, causing incorrect median calculation
Fix: Always check and balance the heaps sizes after each insertion to keep size difference at most one

Mistake: Adding all numbers to one heap only
Fix: Use condition to decide which heap to add the number to keep halves separated

Summary

Maintains two heaps to quickly find the median of a data stream.

Use when you need fast median queries on a continuously growing list.

The median is always at the top of one or both heaps, so keep them balanced.