Find Median from Data Stream — Two-Heap Streaming Pattern

Problem Statement#

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Constraints:

• -10^5 <= num <= 10^5
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 10^4 calls to addNum and findMedian.

MedianFinder mf;
mf.addNum(1); mf.addNum(2);
mf.findMedian(); // 1.5
mf.addNum(3);
mf.findMedian(); // 2.0

Why This Problem Matters#

LeetCode 295 Find Median from Data Stream is the canonical "running median" interview problem and shows up at Amazon, Google, Meta, Bloomberg, and Two Sigma. It is a foundational streaming algorithms question that tests whether you can compose two priority queues into a balanced data structure.

Real-world analogues are everywhere: real-time latency dashboards (p50 over rolling windows), trading risk monitors (median of order sizes), sensor calibration (median to suppress outliers). The two-heap pattern is also the building block for sliding window median (LeetCode 480) and IPO-style scheduling (LeetCode 502).

The interview signal is high because the obvious solutions (sorted list with insort or BST) cost O(n) or O(log n) per addNum but with O(log n) findMedian — only the two-heap pattern hits O(log n) addNum and O(1) findMedian, and it forces the candidate to maintain a non-trivial size invariant.

The Core Insight#

Maintain two heaps:

• low: a max-heap of the smaller half of the stream.
• high: a min-heap of the larger half.

Invariants after every addNum:

1. Every element in low is less than or equal to every element in high.
2. abs(len(low) minus len(high)) is at most 1.

If invariant 2 is preserved with low having one more element, the median is low's max. If sizes are equal, the median is the average of low's max and high's min.

addNum logic:

• Push to low. Then push the max of low onto high (this restores invariant 1).
• If high's size now exceeds low's size, push the min of high back to low (this restores invariant 2).

This balancing dance takes O(log n) per addNum. findMedian is O(1).

Python's heapq is a min-heap, so we negate values to simulate a max-heap for low.

Visual Dry Run#

Stream: 1, 2, 3.

Initial: low = [], high = [].

addNum(1): push -1 to low. Low = [-1] (i.e., max-heap top is 1). Move max of low (1) to high. Low = [], high = [1]. Sizes 0 vs 1; high larger by 1. Pop high's min (1), push to low. Low = [-1], high = []. Final sizes: low = 1, high = 0.

findMedian after one element returns 1.0. (Note: the test sequence calls findMedian only after enough elements.)

addNum(2): push -2 to low. Low = [-2, -1] (top 2). Move 2 to high. Low = [-1], high = [2]. Sizes 1 vs 1, balanced.

findMedian: equal sizes, return (1 + 2) / 2 = 1.5.

addNum(3): push -3 to low. Low = [-3, -1] (top 3). Move 3 to high. Low = [-1], high = [2, 3]. Sizes 1 vs 2; high larger. Pop high's min (2), push to low. Low = [-2, -1], high = [3]. Sizes 2 vs 1.

findMedian: low has more, return low max equal to 2.0.

Matches expected outputs.

Solution (Optimal)#

import heapq
from typing import List
 
class MedianFinder:
    def __init__(self):
        self.low: List[int] = []   # max-heap (negated values)
        self.high: List[int] = []  # min-heap
 
    def addNum(self, num: int) -> None:
        # 1. Tentatively put num on low (max-heap)
        heapq.heappush(self.low, -num)
        # 2. Move max of low to high to maintain ordering invariant
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # 3. Rebalance sizes
        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.0

// JavaScript has no built-in heap; we implement a small binary heap.
class MinHeap {
  constructor(cmp = (a, b) => a - b) { this.h = []; this.cmp = cmp; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(this.h[i], this.h[p]) < 0) {
        [this.h[i], this.h[p]] = [this.h[p], this.h[i]];
        i = p;
      } else break;
    }
  }
  pop() {
    const top = this.h[0], last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < this.h.length && this.cmp(this.h[l], this.h[s]) < 0) s = l;
        if (r < this.h.length && this.cmp(this.h[r], this.h[s]) < 0) s = r;
        if (s !== i) { [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s; }
        else break;
      }
    }
    return top;
  }
}
 
class MedianFinder {
  constructor() {
    this.low = new MinHeap((a, b) => b - a);   // max-heap
    this.high = new MinHeap((a, b) => a - b);  // min-heap
  }
  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;
  }
}

Complexity. addNum is O(log n). findMedian is O(1). Space is O(n).

Common Mistakes#

• Storing all numbers in a sorted list with binary insert. Insert is O(n) due to array shifting.
• Skipping the balancing pass through high. If you push to low only, the ordering invariant breaks.
• Forgetting to negate when using Python heapq for the max-heap.
• Returning low's top when sizes are equal. The correct answer is the average of low's top and high's top.
• Comparing sizes with strict greater-than only — the balancing must restore size difference to at most 1.

Interview Tips#

• Open by stating three approaches (sorted list, BST, two heaps) and their costs. Pick two heaps deliberately.
• Walk through addNum step by step on the whiteboard for two adds and one query.
• Articulate both invariants (ordering and size balance) explicitly. Forgetting one is the most common error.
• Mention that Python's heapq simulates a max-heap by negation; in Java you would pass a reverse comparator to PriorityQueue.
• Discuss the sliding window variant (LeetCode 480) where you must also support delete. Hint: lazy deletion or a balanced BST.

Follow-up Questions#

1. What if numbers are bounded (e.g., 0 to 100)? Use a counting array with O(100) addNum and O(100) findMedian via cumulative count.
2. What if you only need approximate median? Use t-digest or a reservoir sample.
3. Sliding window median over the last k numbers? Use two heaps with lazy deletion or a multiset (C++) or SortedList (Python sortedcontainers).
4. Concurrent stream from multiple threads? Wrap with a mutex or use lock-free heap variants.
5. What if numbers can be removed by id? Use a balanced BST or order-statistic tree.

Key Takeaways#

• Two heaps (max-heap low, min-heap high) give O(log n) addNum and O(1) findMedian.
• Maintain two invariants: every low less than or equal to every high; sizes differ by at most 1.
• Always pass through high after pushing to low to restore ordering.
• Negate values when using Python heapq to simulate a max-heap.
• Pattern extends to sliding window median, IPO scheduling, and many streaming problems.
• Strictly better than sorted list (O(n) insert) for streaming workloads.