208. Find Median from Data Stream

Split the stream at the median: everything below goes into a max-heap low, everything above into a min-heap high. Keep |low| - |high| ∈ {0, 1}.

• |low| == |high| → median = (low.top + high.top) / 2.
• |low| == |high| + 1 → median = low.top.

Python has only min-heaps, so negate values for low.

Approach

On addNum(x):

1. Push x onto low (as -x).
2. Move the largest of low onto high (to keep heaps ordered relative to the median).
3. If high is larger than low, move one back.

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> low;  // max-heap
    private PriorityQueue<Integer> high; // min-heap

    public MedianFinder() {
        low = new PriorityQueue<>(Collections.reverseOrder());
        high = new PriorityQueue<>();
    }

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

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