Find Median from Data Stream

Approach Summary

Maintain a max-heap for the lower half and min-heap for the upper half. Balance their sizes; median is the top of the larger or average of both tops.

Full Solution & Approach

A running median is the boundary between the lower and upper halves of the data, so maintain both halves explicitly with two heaps: a max-heap for the lower half and a min-heap for the upper half. Add each number to the lower max-heap, then rebalance: move the largest of the lower half into the upper half whenever the lower half has more than one extra element, and swap the tops if ordering is violated. The invariant is that both halves differ in size by at most one and every value in the lower half is at most every value in the upper half. The median is then the top of the larger heap, or the average of the two tops when sizes are equal. Each add does O(log n) heap work; the median is read in O(1). The two-heaps pattern is the standard answer for streaming percentile questions.

Each add performs at most a constant number of O(log n) heap operations — O(log n) per add. Both heaps together store n elements — O(n) space.

Solution Code

Solution

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (negated)
        self.high = []  # min-heap

    def add_num(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

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

class MedianFinder {
  constructor() {
    this.low = [];  // max-heap via negation
    this.high = []; // min-heap
  }
  push(heap, v) {
    heap.push(v);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p] <= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }
  pop(heap) {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l] < heap[s]) s = l;
        if (r < heap.length && heap[r] < heap[s]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]];
        i = s;
      }
    }
    return top;
  }
  addNum(num) {
    this.push(this.low, -num);
    this.push(this.high, -this.pop(this.low));
    if (this.high.length > this.low.length) {
      this.push(this.low, -this.pop(this.high));
    }
  }
  findMedian() {
    if (this.low.length > this.high.length) return -this.low[0];
    return (-this.low[0] + this.high[0]) / 2;
  }
}

class MedianFinder {
    private PriorityQueue<Integer> low = new PriorityQueue<>((a, b) -> b - a);   // max-heap
    private PriorityQueue<Integer> high = new PriorityQueue<>();                 // min-heap

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) low.offer(high.poll());
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2.0;
    }
}

class MedianFinder {
    priority_queue<int> low;                    // max-heap
    priority_queue<int, vector<int>, greater<int>> high;  // min-heap
public:
    void addNum(int num) {
        low.push(num);
        high.push(low.top());
        low.pop();
        if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        }
    }
    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return (low.top() + high.top()) / 2.0;
    }
};

Edge Cases to Watch

Empty stream — the problem guarantees findMedian is never called on an empty structure
Odd count — the larger heap holds the median at its top
Even count — average of the two tops
Duplicate values — heaps store every copy

How to Recognize This Pattern

Running median
Two heaps pattern

Complexity Analysis

Time Complexity

O(log n) add, O(1) median

Space Complexity

O(n)