Skip to main content
Advanced

Find Median from Data Stream

hardHeaps (hard) Must-doGoogle SREUberDatadog

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) — adds num to 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

Hint 1: If you kept the numbers sorted at all times, the median would always be readable directly from the middle position (or the two middle positions) — the hard part is keeping them sorted efficiently as new numbers keep arriving.

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

  1. Keep two heaps: small (a max-heap) for the lower half, large (a min-heap) for the upper half.
  2. addNum(num): push num onto small first, then immediately pop small's new maximum and push it onto large — this guarantees every value in small stays less than or equal to every value in large, regardless of where num actually belonged.
  3. If large now has more elements than small, move large's minimum back into small — this keeps the two heaps balanced, with small allowed to have at most one more element than large.
  4. findMedian(): if small has more elements than large, return small's top directly (it's the single middle value). Otherwise (equal sizes), return the average of small's top and large'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. addNum increments the bucket for that value in O(1). findMedian walks 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 addNum calls 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.