Typorithm · hard

Median of Data Stream

median-of-data-streamheapstwo-heapsbalancerunning-median

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Median of Data Stream

Heaps

Keep a max-heap of the low half and a min-heap of the high half, balanced so the median is one or both heap tops.

The median splits the data into a lower and an upper half.

A max-heap holds the lower half (its top is the largest small value) and a min-heap holds the upper half.

Each insert funnels through low into high, then rebalances sizes, so the median is low's top (odd count) or the average of both tops (even).

Max-heap low, min-heap high.

Push low → pop to high → rebalance.

Median = top(s) of the heaps.

class MedianFinder {
  constructor() {
    this.low = new MaxHeap();
    this.high = new MinHeap();
  }

  addNum(num) {
    this.low.push(num);
    this.high.push(this.low.pop());
    if (this.high.size() > this.low.size()) {
      this.low.push(this.high.pop());
    }
  }

  findMedian() {
    if (this.low.size() > this.high.size()) {
      return this.low.peek();
    }
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Two halves

A max-heap holds the lower half; a min-heap holds the upper half.

this.low = new MaxHeap();
    this.high = new MinHeap()

2. Funnel through low

Push to low, then move its max to high to keep order correct.

this.low.push(num);
    this.high.push(this.low.pop())

3. Rebalance sizes

Keep low at least as large as high so its top is the median.

if (this.high.size() > this.low.size()) {
      this.low.push(this.high.pop());
    }

4. Even-count median

With equal halves, average the two heap tops.

return (this.low.peek() + this.high.peek()) / 2

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.