Find Median from Data Stream
Problem Statement
Design a MedianFinder data structure that receives integers one at a time. addNum(num) adds a number from the stream, and findMedian() returns the median of all numbers seen so far. If the count is even, the median is the average of the two middle numbers.
Input
A constructor call MedianFinder() followed by a sequence of addNum(num) and findMedian() calls.
Output
For the constructor and addNum, output null. For findMedian, output the current median as a double.
Constraints
- •
-10^5 <= num <= 10^5 - •
At most 5 * 10^4 calls will be made to addNum and findMedian - •
At least one number has been added before findMedian is called
Examples
Example 1
operations = [MedianFinder, addNum, addNum, findMedian, addNum, findMedian], arguments = [[], [1], [2], [], [3], []]
[null, null, null, 1.5, null, 2.0]Example 2
operations = [MedianFinder, addNum, findMedian, addNum, addNum, findMedian], arguments = [[], [5], [], [15], [1], []]
[null, null, 5.0, null, null, 5.0]Learning Objectives
- Recognise the running-median signal in a data stream problem.
- Split values into a lower half max-heap and an upper half min-heap.
- Maintain ordering and size invariants after every insertion.
- Compute an odd or even median directly from heap roots in O(1).
Intuition
Pattern Recognition
The signal is a stream of numbers with repeated median queries. Sorting after every insertion is too expensive, and inserting into the middle of an array shifts many elements. The median only needs the boundary between the smaller half and the larger half, not a fully sorted list.
Use two heaps split around that boundary. A max-heap named low stores the lower half so its root is the largest small value. A min-heap named high stores the upper half so its root is the smallest large value. If the halves are balanced, those one or two roots are exactly the median candidates.
Common mistakes
- ×Keeping one sorted list and paying O(n) insertion for every **addNum**.
- ×Letting one heap grow by more than one element, which moves the root away from the median boundary.
- ×Putting the larger half in a max-heap or the lower half in a min-heap, then peeking at the wrong boundary.
- ×Averaging two integer roots before converting to double, which can truncate or overflow on related variants.
Algorithm Explanation
Key idea
Keep two heaps with two precise invariants. First, every value in low is less than or equal to every value in high. Second, low.size() is either equal to high.size() or exactly one larger. This implementation lets low hold the extra value when the count is odd. Therefore findMedian() returns low.peek() for odd counts, and the average of low.peek() and high.peek() for even counts. More generally, the median is the root of the larger heap or the average of both roots when sizes match.
Heap walkthrough
Trace the stream [5,15,1,3]. Add 5 into low, so low = [5], high = [], and the median is 5. Add 15 into high, giving low = [5], high = [15], so the median is the average of the two roots. Add 1 into low because it belongs to the smaller half; now low = [5,1], high = [15], and the median is the root 5. Add 3 into low, making it too large: low = [5,1,3], high = [15]. Rebalance by moving root 5 from low to high, leaving low = [3,1], high = [5,15], so the median is (3 + 5) / 2 = 4.
Algorithm
- Store the lower half in a max-heap low and the upper half in a min-heap high.
- For addNum(num), insert into low if low is empty or num <= low.peek(); otherwise insert into high.
- If low has more than one extra element, move low.peek() to high.
- If high has more elements than low, move high.peek() to low.
- For findMedian(), return low.peek() when low is larger; otherwise return the double average of the two roots.
Solutions
Solution: Two heaps with balanced halves
Use this when numbers arrive online and every query must be answered without re-sorting the full prefix.
The max-heap low exposes the largest value in the lower half, while the min-heap high exposes the smallest value in the upper half. Rebalancing after each insert keeps the median at one or two roots.
Step-by-step
- Initialise low as a max-heap and high as a min-heap.
- Insert each new number into the heap whose half it belongs to by comparing against low.peek().
- Move one root across if the size invariant is broken.
- When asked for the median, use low.peek() if the total count is odd.
- When the heaps are equal in size, return the double average of both roots.
addNum: O(log n), findMedian: O(1)
O(n)
Each inserted number lives in exactly one heap; rebalancing moves at most one root.
Java implementation
Dry Run
Sample input
Stream: addNum(5), addNum(15), addNum(1), addNum(3). Heaps are shown with their root first.
| op | low | high | median |
|---|---|---|---|
| addNum(5) | [5] | [] | 5.0 |
| addNum(15) | [5] | [15] | 10.0 |
| addNum(1) | [5,1] | [15] | 5.0 |
| addNum(3) | [3,1] | [5,15] | 4.0 |
After the final insertion, rebalancing moved 5 to high, so the two roots 3 and 5 frame the middle and average to 4.0.
Interview Tips
Say the invariants before coding: low contains the lower half, high contains the upper half, every low value is <= every high value, and sizes differ by at most one. Then the median formula becomes obvious. Use a safe average expression in Java even if this problem's value range is small, because interviewers often widen the range in follow-ups.
Likely follow-ups
- How would you remove an arbitrary old value when the stream becomes a sliding window?
- How would the design change if you needed the 25th percentile instead of the median?
- Could a balanced binary search tree replace the two heaps?
- How would you make **findMedian()** thread-safe while insertions continue?
Similar Problems
Key Takeaways
- A running median does not require fully sorting every prefix.
- The lower half needs a max-heap and the upper half needs a min-heap.
- The size invariant is what keeps the median at one or two roots.
- Insertions are O(log n), while median queries are O(1).