Find Median from Data Stream

Numbers arrive one at a time. Design a class MedianFinder that can report the median of everything it has received so far:

• MedianFinder() starts with no numbers.
• addNum(num) records one more integer.
• findMedian() returns the median of all numbers recorded so far. It is only called after at least one addNum.

The median is the middle value once the numbers are sorted. When the count is even there are two middle values, and the median is their average, which may be a fraction (the median of 2, 3, 7, 8 is 5.5). Answers within 10^-5 of the true median are accepted.

Each test lists the method calls and their arguments; the output holds every return value, with null for the constructor and addNum.

Example 1

Example 2

Example 3

Constraints

• -105 <= num <= 105
• findMedian is only called after at least one number has been added.
• At most 5 · 104 calls are made in total.

Pattern Path · Heaps & Top-K · problem 106 of 169

Start simple

Keep a list, append each number and sort (or insert in order) on each call: O(n log n) or O(n) per operation.

The key idea

The median only depends on the boundary between the smaller half and the larger half of the numbers. So keep the two halves in two heaps:

• low: a max-heap with the smaller half, so its top is the largest of the small numbers.
• high: a min-heap with the larger half, so its top is the smallest of the large numbers.

Maintain two rules: every value in low is <= every value in high, and low holds either the same number of items as high or exactly one more.

To add a number, push it into low, then move low's top to high. This routes the number to the correct side and keeps the halves ordered. If high is now bigger, move its top back to low. Each step is a few heap operations, O(log n).

The median is then read straight off the tops: low's top if the total count is odd, otherwise the average of both tops. That is O(1).

Complexity

• Time: O(log n) per addNum, O(1) per findMedian
• Space: O(n)

Python

import heapq


class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap of the smaller half (values stored negated)
        self.high = []  # min-heap of the larger half

    def addNum(self, num: int) -> None:
        # Route the number through the lower half so the halves stay ordered...
        heapq.heappush(self.high, -heapq.heappushpop(self.low, -num))
        # ...then rebalance: low may hold at most one more item than high.
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

JavaScript

class Heap {
  constructor(before) {
    this.items = [];
    this.before = before;  // before(a, b) is true when a belongs above b
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(x) {
    const a = this.items;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!this.before(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = l + 1;
        let best = i;
        if (l < a.length && this.before(a[l], a[best])) best = l;
        if (r < a.length && this.before(a[r], a[best])) best = r;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return top;
  }
}

class MedianFinder {
  constructor() {
    this.low = new Heap((a, b) => a > b);   // max-heap of the smaller half
    this.high = new Heap((a, b) => a < b);  // min-heap of the larger half
  }

  addNum(num) {
    // Route the number through the lower half so the halves stay ordered...
    this.low.push(num);
    this.high.push(this.low.pop());
    // ...then rebalance: low may hold at most one more item than high.
    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;
  }
}

What the interviewer is checking

This checks whether you can pick heaps to expose exactly the order statistic you need, and keep two invariants (ordering and size balance) correct after every insertion.

Mistakes to avoid

• Pushing a new number straight into one heap without checking it belongs there, which breaks the ordering between halves.
• Letting the heap sizes drift apart by more than one.
• Using integer division for the average of the two middle values, losing the .5.
• Forgetting to negate values when simulating a max-heap with a min-heap library.

Follow-ups to expect

• What if all numbers lie in 0..100? (Counting array, O(100) query.)
• What if you need the median of only the last k numbers? (Two heaps with lazy deletion.)
• What if the stream is too big for one machine? (Approximate quantiles, e.g. t-digest.)

In real software

Monitoring systems report median (p50) latency over a live stream of request times, and trading systems track a running median price, both without re-sorting history on every update.

Practice next