Find Median from Data Stream (LC 295)

Pattern: Two Heaps (Lazy Balancing)
Difficulty: Hard
Key Concept: Keep lower half in a max-heap and upper half in a min-heap; sizes differ by at most 1; median from tops.

Problem Statement

The median is the middle value in an ordered list. If the size is even, median is the average of the two middle values.

Implement:

• MedianFinder() — initializer
• void addNum(int num) — add integer from stream
• double findMedian() — return median of all elements so far

Input: stream of integers (can be negative).
Output: double median.

---

1. Algorithm & Pseudocode

Brute force

1. Store all numbers in ArrayList, sort on every findMedian — add O(1) amortized, query O(n log n).

Pseudocode

data = []
addNum(x): data.add(x)

findMedian():
    sort(data)
    if odd: return middle
    else: return avg(middle-1, middle)

Optimal

1. maxHeap holds the smaller half (largest on top).
2. minHeap holds the larger half (smallest on top).
3. Balance: after each insert, ensure maxHeap.size() == minHeap.size() or maxHeap has one extra (convention).
4. addNum:
   • Add to maxHeap first (or compare tops — many valid variants).
   • Rebalance by moving tops between heaps until size invariant holds.
5. findMedian:
   • If total odd: top of maxHeap.
   • Else: average of tops of both heaps.

Pseudocode

maxH, minH

addNum(x):
    maxH.add(x)
    move maxH.top to minH if needed to keep order
    if minH.size > maxH.size:
        move minH.top to maxH
    // invariant: maxH.size == minH.size or maxH.size == minH.size + 1

findMedian():
    if maxH.size > minH.size: return maxH.top
    else: return (maxH.top + minH.top) / 2.0

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Heaps give O(log n) inserts and O(1) access to one extreme — perfect for maintaining running middles.
• Why two heaps: One sorted structure alone is expensive to keep fully sorted on each insert; heaps approximate partition into low/high halves.
• Balancing ensures the true median (or the two center values) always sit at heap tops.
• Java: PriorityQueue is a min-heap; simulate max-heap with Collections.reverseOrder() or negating values (careful with overflow for negatives).

---

3. The Dry Run

Using the optimal code pattern: every addNum does low.offer(num); high.offer(low.poll()); if (high.size() > low.size()) low.offer(high.poll());

Here low is the max-heap (smaller half), high is the min-heap (larger half).

Step	num	After low.offer + high.offer(low.poll())	Rebalance (high bigger?)	low (max-heap peek)	high (min-heap peek)	findMedian()
1	1	low=[], high=[1]	yes → move 1 to low	1	—	1.0
2	2	low=[2,1], then top 2 goes to high → low=[1], high=[2]	no	1	2	(1+2)/2 = 1.5
3	3	low=[3,1], move top 3 → low=[1], high=[2,3]	yes → move 2 to low → low=[2,1], high=[3]	2	3	2.0 (low has extra)

ASCII (after 1, 2, 3)

smaller half (max-heap `low`)     larger half (min-heap `high`)

        2  ← peek                         3  ← peek
       /
      1

All added values {1,2,3} → median is middle value 2

---

4. Java Solution

Brute Force

import java.util.*;

class MedianFinderBrute {
    private final List<Integer> data = new ArrayList<>();

    public MedianFinderBrute() {}

    public void addNum(int num) {
        data.add(num);
    }

    // findMedian: O(n log n)
    public double findMedian() {
        Collections.sort(data);
        int n = data.size();
        if ((n & 1) == 1) return data.get(n / 2);
        return (data.get(n / 2 - 1) + data.get(n / 2)) / 2.0;
    }
}

Optimal

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> high = new PriorityQueue<>();

    public MedianFinder() {}

    // addNum: O(log n)
    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) {
            low.offer(high.poll());
        }
    }

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

---

5. The “Java vs. Others” Edge

• PriorityQueue<Integer> with Collections.reverseOrder() is the clean max-heap.
• Negation trick pq.offer(-x) breaks for Integer.MIN_VALUE edge cases — prefer reverseOrder.
• peek() does not remove; poll() does.
• For very large streams, consider balanced BST / order-statistic tree (not in JDK standard).

---

6. Complexity Summary

Approach	addNum	findMedian	Space
Brute sort on query	O(1)	O(n log n)	O(n)
Two heaps	O(log n)	O(1)	O(n)