Find Median from Data Stream
Problem statement
Numbers arrive one at a time, and at any moment you need to be able to report the median of every number seen so far — the middle value if the count is odd, or the average of the two middle values if it's even. Both adding a number and asking for the current median need to be fast, since either can be called many times as the stream grows.
Implement a MedianFinder class with:
MedianFinder()— creates an empty finder.addNum(num)— addsnumto the running collection of numbers seen.findMedian()— returns the median of every number added so far.
Think of it as a live latency dashboard: as request-time readings stream in, you want the current median response time available instantly at any moment, not recomputed from scratch by re-sorting every reading each time someone checks.
Examples
Example 1
Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output: [null, null, null, 1.5, null, 2.0]
Explanation: MedianFinder() starts empty. addNum(1) then addNum(2) leave the numbers {1, 2}. findMedian() returns 1.5, the average of the two middle values (there's no single middle value with an even count). addNum(3) gives {1, 2, 3}. findMedian() now returns 2.0, the single middle value of the three.
Hints
Approach
Optimal: Two heaps
Intuition
You never actually need the numbers fully sorted — the median only cares
about the boundary between the lower half and the upper half of the data.
So split the numbers into two groups: small, holding the lower half, and
large, holding the upper half, keeping them balanced in size (differing
by at most one element). The value that matters most in small is its
largest value (the top of the lower half, right at the boundary), so
store it as a max-heap. The value that matters most in large is its
smallest value, so store it as a min-heap. The median is then either the
top of whichever heap has one more element, or the average of both tops
when the sizes are equal — no sorting needed at all.
Steps
- Keep two heaps:
small(a max-heap) for the lower half,large(a min-heap) for the upper half. addNum(num): pushnumontosmallfirst, then immediately popsmall's new maximum and push it ontolarge— this guarantees every value insmallstays less than or equal to every value inlarge, regardless of wherenumactually belonged.- If
largenow has more elements thansmall, movelarge's minimum back intosmall— this keeps the two heaps balanced, withsmallallowed to have at most one more element thanlarge. findMedian(): ifsmallhas more elements thanlarge, returnsmall's top directly (it's the single middle value). Otherwise (equal sizes), return the average ofsmall's top andlarge's top.
Dry run
addNum(1), addNum(2), then findMedian(), then addNum(3), then
findMedian():
| call | small (max-heap) | large (min-heap) | detail |
|---|---|---|---|
| addNum(1) | {1} | {} | push 1 to small, pop its max (1) to large, then large > small? no (0 vs 1, wait large now has 1, small has 0) → rebalance: large(1) > small(0) → move large's min (1) back to small |
| after rebalance | {1} | {} | small=[1], large=[] |
| addNum(2) | push 2 to small → {1,2}, pop max (2) to large → small={1}, large={2} | balanced (1 and 1), no rebalance needed | small=[1], large=[2] |
| findMedian() | sizes equal (1, 1) | — | (1 + 2) / 2 = 1.5 |
| addNum(3) | push 3 to small → {1,3}, pop max (3) to large → small={1}, large={2,3}; large(2) > small(1) → move large's min (2) back to small | small={1,2}, large={3} | |
| findMedian() | small has more elements (2 vs 1) | — | return small's top = 2.0 |
Both answers match the brute-force approach's results, but findMedian
never sorted anything — it only ever read the top of one or two heaps.
Edge cases: the very first addNum call always leaves small with one
element and large empty (the rebalancing step handles this the same way
as any other case, with no special-casing needed), and findMedian after
just one number correctly falls into the "sizes not equal" branch and
returns that single value.
Complexity
Time Both - `addNum` and `findMedian` are O(log m) and O(1) respectively — `addNum` does a constant number of heap pushes and pops, each O(log m); `findMedian` just reads the top of one or both heaps.
Space O(m) - every number is stored in one of the two heaps.
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (as negated values) for the lower half
self.large = [] # min-heap for the upper half
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
# Make sure every value in `small` is <= every value in `large`.
heapq.heappush(self.large, -heapq.heappop(self.small))
# Keep the sizes balanced: `small` may have at most one more than `large`.
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2.0
if __name__ == "__main__":
mf = MedianFinder()
out = [None]
mf.addNum(1); out.append(None)
mf.addNum(2); out.append(None)
out.append(mf.findMedian())
mf.addNum(3); out.append(None)
out.append(mf.findMedian())
print(out)RecapThe whole problem in a few lines, for the night before
- Spot it: numbers arrive one at a time and you need the median after each one
- Idea: keep the lower half in a max-heap and the upper half in a min-heap; the median is at the top of one heap or the average of both tops
- Cost: O(log n) per add, O(1) to read the median, O(n) space
- Trap: forgetting to rebalance, so the heap sizes drift apart by more than 1
Interview follow-ups
If all the numbers in the stream are guaranteed to be integers between 0 and 100, how would you optimize this?
Use a fixed-size counting array of 101 buckets, one per possible value.
addNumincrements the bucket for that value in O(1).findMedianwalks the buckets from the smallest value upward, accumulating counts until crossing the middle position(s) — bounded by 101 buckets regardless of how many numbers have been added, so it costs O(1) relative to the stream's size (though technically O(range) rather than O(1) in the strictest sense).If 99% of the numbers are in the range [0, 100], but a small fraction can be anything else, how would you optimize for that?
Combine both ideas: keep the counting-array approach above for values inside [0, 100], and fall back to the two-heap approach only for the rare values outside that range. Since the vast majority of
addNumcalls stay inside the fast path, the overall cost stays close to the counting array's O(1)-per-call behavior, with the two-heap structure only ever holding a small number of outliers.
Frequently asked questions
It's tempting to compare the new number to the current median and push it
straight into whichever heap it "obviously" belongs to, but that logic
gets subtly wrong at the boundary case (a new number equal to or very
close to the current median). Pushing onto small first and then always
moving small's new maximum over to large sidesteps that entirely — it
always produces a correct split regardless of where the new number
actually landed, at the cost of one extra pop/push pair. That's a small
price for not having to reason about edge cases separately.
It's an arbitrary but consistent choice — the important thing is that
exactly one of the two heaps is allowed a one-element lead, so that
findMedian has an unambiguous rule for the odd-count case (always read
from small's top). Letting large hold the extra element instead would
work identically, as long as findMedian is updated to match.
Shifting is a plain loop, not something asymptotically free — inserting
into the middle of an array-backed list of length m touches up to m
elements to make room. With up to 5 × 10⁴ calls to addNum, as the
constraints allow, a running total of O(m²) work across all inserts adds
up quickly compared to the two-heap approach's O(m log m) total. This is
exactly the kind of gap that matters more as the stream grows longer.
A live median is a much more robust "typical value" than a live average for things like response times or queue depths, since outliers barely move it — and computing it instantly on every new reading, without re-sorting a growing history each time, is exactly the shape of a real-time monitoring or alerting requirement.