# Find Median from Data Stream

- **Canonical ID**: `find-median-from-data-stream`
- **Canonical URL**: https://dsacheatsheet.com/problems/find-median-from-data-stream
- **Difficulty**: hard
- **Patterns**: Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/find-median-from-data-stream/

## 1. Core Invariant / The Trick

Maintain two balanced heaps: `lo` (max-heap of lower half) and `hi` (min-heap of upper half). Preserve two invariants on every `addNum`: (1) `max(lo) <= min(hi)`, and (2) `len(lo) >= len(hi)` differing by at most 1. Cleanest 3-step push: push into `lo`, pop `max(lo)` to `hi`, and if `len(hi) > len(lo)` pop `min(hi)` back to `lo`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log N)`
- **Space Complexity**: `O(N)`
- **Proof**: Three-step push guarantees ordering and size invariants without conditional branches on comparison; `findMedian` is O(1).

## 3. Minimal Idiomatic Code

### Python
```python
class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap via negation
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0
```

### TypeScript
```typescript
export class MedianFinder {
  private lo: number[] = []; // max-heap
  private hi: number[] = []; // min-heap
  private push(h: number[], v: number, cmp: (a: number, b: number) => boolean) {
    h.push(v);
    for (let i = h.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (cmp(h[p], h[i])) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }
  private pop(h: number[], cmp: (a: number, b: number) => boolean): number {
    const top = h[0], last = h.pop()!;
    if (h.length) {
      h[0] = last;
      for (let i = 0; ; ) {
        let b = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && cmp(h[l], h[b])) b = l;
        if (r < h.length && cmp(h[r], h[b])) b = r;
        if (b === i) break;
        [h[i], h[b]] = [h[b], h[i]];
        i = b;
      }
    }
    return top;
  }
  addNum(num: number): void {
    const maxC = (a: number, b: number) => a >= b;
    const minC = (a: number, b: number) => a <= b;
    this.push(this.lo, num, maxC);
    this.push(this.hi, this.pop(this.lo, maxC), minC);
    if (this.hi.length > this.lo.length) this.push(this.lo, this.pop(this.hi, minC), maxC);
  }
  findMedian(): number {
    return this.lo.length > this.hi.length ? this.lo[0] : (this.lo[0] + this.hi[0]) / 2;
  }
}
```

### C++
```cpp
class MedianFinder {
    priority_queue<int> lo;
    priority_queue<int, vector<int>, greater<int>> hi;
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        return lo.size() > hi.size() ? lo.top() : (lo.top() + hi.top()) / 2.0;
    }
};
```

### Java
```java
class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> hi = new PriorityQueue<>();
    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (hi.size() > lo.size()) lo.offer(hi.poll());
    }
    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}
```

### Go
```go
type MedianFinder struct { lo MaxHeap; hi MinHeap }
func (mf *MedianFinder) AddNum(num int) {
    heap.Push(&mf.lo, num)
    heap.Push(&mf.hi, heap.Pop(&mf.lo))
    if mf.hi.Len() > mf.lo.Len() { heap.Push(&mf.lo, heap.Pop(&mf.hi)) }
}
func (mf *MedianFinder) FindMedian() float64 {
    if mf.lo.Len() > mf.hi.Len() { return float64(mf.lo[0]) }
    return float64(mf.lo[0]+mf.hi[0]) / 2.0
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Comparing new value directly against heap tops creates fragile branching.
- Integer division `(lo[0] + hi[0]) / 2` in C++/Java without `.0` / `2.0` truncates `.5`.

### Follow-ups
- If all numbers are in `[0, 100]`, use a 101-bucket counting array for O(1) `findMedian`.