Find Median from Data Stream
Find Median from Data Stream is LeetCode 295 (Hard). Design a MedianFinder class:
addNum(num)adds an integer from the stream.findMedian()returns the median of every number added so far: the middle value, or the average of the two middle values when the count is even.
Up to 5 · 10⁴ calls mix the two operations, so sorting again for every query is too slow; both operations need to be fast.
- -10⁵ <= num <= 10⁵
- There will be at least one element in the data structure before calling findMedian.
- At most 5 * 10⁴ calls will be made to addNum and findMedian.
Intuition
A median depends only on the middle of the sorted order, never on the rest. So split the numbers into two halves and keep just enough order to see the middle, using two heaps:
- Lower half: a max-heap, so its top is the largest small number.
- Upper half: a min-heap, so its top is the smallest large number.
Keep every lower value ≤ every upper value, and keep the lower half the same size as the upper half or one bigger. Then the two tops sit right at the middle: the median is the lower top (odd count) or the average of both tops (even count).
Any running median of a stream, or a sliding-window median, is the two-heaps pattern: split the data at the answer and keep each half in a heap whose top faces the middle. The same idea finds the k-th smallest value of a stream with a single heap of size k.
Approach
Before reading on: after adding 5, 15, 1 and 3, which two numbers decide the median? What is the least order you must keep to find them again after each new number?
Set up two heaps
lo is a max-heap for the smaller half, hi a min-heap for the larger half. Python's heapq only builds min-heaps, so lo stores negated values and flips the sign back on the way out. C++ and Java use a reversed comparator.
Push the new number through lo
Push num into lo, then pop the largest value of lo and push it into hi. Whatever num was, the biggest value of the lower half ends up in the upper half, so every value in lo stays ≤ every value in hi without a single comparison.
Rebalance the sizes
The previous step always makes hi one bigger. If hi now has more values than lo, pop its smallest value and push it back into lo. This keeps lo the same size as hi or exactly one bigger, so the median's position never moves.
Read the median from the tops
If lo is bigger, the count is odd and the median is the top of lo. Otherwise average the two tops as a decimal, (lo top + hi top) / 2.0. In C++ and Java, dividing by the integer 2 would turn 1.5 into 1.
Find Median from Data Stream solution in Python | C++ | Java
Common pitfalls
Putting the lower half in a min-heap
heapq.heappush(self.lo, num)
heapq.heappush(self.lo, -num)
The lower half must expose its largest value. A plain heapq list exposes the smallest, so its top is the smallest number seen, not the middle. Python stores negatives to fake a max-heap, and every value must flip sign again when it leaves lo.
Skipping the rebalance
heapq.heappush(self.lo, -num) heapq.heappush(self.hi, -heapq.heappop(self.lo))
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))Every insert moves one value into hi, so without the last step lo never keeps anything and stays empty. The first findMedian then reads the top of an empty heap and crashes.
Integer division on an even count
return (lo.top() + hi.top()) / 2;
return (lo.top() + hi.top()) / 2.0;
In C++ and Java, int / int drops the fraction, so the median of 1 and 2 comes back as 1 instead of 1.5. Dividing by 2.0 keeps the decimal.
Complexity
addNum does at most three heap pushes or pops; findMedian only reads the tops. Every number is stored. Sorting on each query would cost O(n log n) per call.Find Median from Data Stream FAQ
What if every number is between 0 and 100?
Keep a count array of 101 slots instead of heaps. addNum is one increment, O(1). findMedian walks the counts until it reaches the middle position, at most 101 steps, which is O(1) for a fixed range.
What if 99% of the numbers are between 0 and 100?
Use the count array for values in range, plus two counters (or small sorted lists) for values below 0 and above 100. The median almost always lands inside the range, so the walk over the counts still finds it; the rare outliers only shift which position you look for.
Why not insert into a sorted list with binary search?
Finding the position is O(log n), but inserting into the middle of an array shifts up to n values, so each addNum is O(n); this is the insertion-sort approach, O(n²) over the whole stream. A balanced sorted set (C++ multiset, Java TreeMap) with a pointer to the middle also gets O(log n) per insert, but moving that pointer correctly is fiddly. Two heaps give the same O(log n) with simpler code.