#295
Find Median from Data Stream
Hard Two heaps
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a structure that adds numbers from a stream and returns the median of all numbers so far at any time.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the median after every new number.
Why this works: a max-heap holds the smaller half and a min-heap the larger half; the median is at the tops.
Example: add 1, 2, 3
low {1}, high {} → 1low {1}, high {2} → 1.5low {2, 1}, high {3} → 2
✦Hints open one at a time
Keep the smaller half in a max-heap and the larger half in a min-heap.
Balance them so their sizes differ by at most one.
↗Approach
addNum: push into the max-heap (low), move low's top to the min-heap (high), and if high becomes bigger than low, move high's top back. The median is low's top (odd count) or the average of both tops.
</>Solution (Java)
import java.util.*;
class MedianFinder {
private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
private final PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap
public void addNum(int num) {
low.offer(num);
high.offer(low.poll()); // largest of the low half moves up
if (high.size() > low.size()) low.offer(high.poll()); // keep low >= high in size
}
public double findMedian() {
if (low.size() > high.size()) return low.peek();
return (low.peek() + (double) high.peek()) / 2;
}
}!Common mistake
Adding to one heap based only on size and not passing through the other heap — the halves can end up out of order.
Complexity
- Time: O(log n) add, O(1) median.
- Space: O(n).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon