Find Median from Data Stream

Table of Contents +

Numbers keep coming in one at a time. After each one you must tell the median right away. You cannot wait for all the numbers first. This question looks scary but it has a clean trick. The interviewer wants to see if you can keep data balanced as it grows.

🎯 The Problem

A median is the middle value of a sorted list, and the numbers arrive one at a time.

What the median means:

If the count is odd, the median is the single middle value.
If the count is even, the median is the average of the two middle values.

The hard part:

Numbers arrive as a stream, one by one over time.
After each new number you must return the current median fast.
You cannot wait for all the numbers first.

Input:  add 1, add 2, find median, add 3, find median
Output: 1.5, 2.0

Explanation:
After 1, 2 -> sorted [1, 2] -> median = (1 + 2) / 2 = 1.5
After 1, 2, 3 -> sorted [1, 2, 3] -> median = 2.0

So every number you add could change the answer. You need a way to find the middle without sorting from scratch each time.

Here is the problem drawn as a flow. Numbers flow in, and at any moment we ask for the middle value.

🐢 Approach 1: Sort Every Time (Brute Force)

The idea in one line: keep every number, then sort and pick the middle on each median call.

The idea:

Store every number in a list.
When asked for the median, sort the list.
Pick the middle value, or average the two middle values.

Why it is weak:

You sort again on every median call.
Each sort is O(n log n).
A stream can be huge, so asking often gets too slow.

Here is the sort-every-time code:

class MedianFinder:
    def __init__(self):
        self.nums = []

    def addNum(self, num):
        self.nums.append(num)

    def findMedian(self):
        nums = sorted(self.nums)
        mid = len(nums) // 2
        if len(nums) % 2:
            return nums[mid]
        return (nums[mid - 1] + nums[mid]) / 2

🐌 Approach 2: Keep the List Sorted (Better)

The idea in one line: insert each number into its sorted spot so the median is always ready.

The idea:

Keep one list that stays sorted as numbers arrive.
Find the correct spot for each new number.
The middle of a sorted list is the median, ready in an instant.

Why it is better but still weak:

Reading the median is now O(1).
But inserting into the right spot shifts elements.
That shift is O(n) per insert. Still slow for a long stream.

Here is the sorted-list code:

import bisect


class MedianFinder:
    def __init__(self):
        self.nums = []

    def addNum(self, num):
        bisect.insort(self.nums, num)

    def findMedian(self):
        mid = len(self.nums) // 2
        if len(self.nums) % 2:
            return self.nums[mid]
        return (self.nums[mid - 1] + self.nums[mid]) / 2

⚡ Approach 3: Two Heaps (Best)

The idea in one line: split the numbers into a small half and a large half so the middle is always at the two tops.

What a heap is:

A heap is a binary tree kept in an array. Each node has at most two children.
A min-heap keeps the smallest value at the top. A max-heap keeps the largest at the top.
Reading the top is instant. Adding or removing is O(log n). It is also called a priority queue.

The setup:

A max-heap holds the smaller half. Its top is the biggest of the small numbers.
A min-heap holds the larger half. Its top is the smallest of the large numbers.
So the two tops sit right next to the middle.

How it works:

After each add, rebalance so the two halves differ by at most one in size.
Equal sizes mean an even count, so the median is the average of the two tops.
One extra number on a side means that top is the median.

Why it is fast:

Each add is O(log n), because each heap push and pop is O(log n).
Reading the median is O(1), because the tops are always ready.

Here is the two-heap layout drawn as a tree. The max-heap on the left, the min-heap on the right.

Steps to Solve

Make a max-heap called low for the smaller half. Make a min-heap called high for the larger half.
To add a number, first push it onto low. Then move the top of low over to high. This keeps low’s values below high’s values.
If high now has more items than low, move the top of high back to low.
For the median, if low has more items, the answer is the top of low.
If both heaps are equal size, the answer is the average of the two tops.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses the heapq module, which gives a min-heap. To make a max-heap we push negative numbers, so the most negative value sits on top.

import heapq


class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (stored as negatives), smaller half
        self.high = []  # min-heap, larger half

    def add_num(self, num):
        heapq.heappush(self.low, -num)              # add to low (negate for max-heap)
        heapq.heappush(self.high, -heapq.heappop(self.low))  # move low top to high
        if len(self.high) > len(self.low):          # rebalance
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]                     # odd count, top of low
        return (-self.low[0] + self.high[0]) / 2.0  # even count, average of tops


mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median())   # 1.5
mf.add_num(3)
print(mf.find_median())   # 2.0

The output of the above code will be:

1.5
2.0

Let us walk through the Python version line by line. The two heaps do all the work.

The low list is the max-heap for the smaller half. Python’s heapq only gives a min-heap. So we store negatives. Pushing -num and reading -self.low[0] flips the order, which gives us a max-heap. The high list is a plain min-heap for the larger half.

In add_num, the first line pushes -num onto low. So the new number goes into the smaller half first. The second line pops the top of low and pushes it onto high. This line matters. It makes sure the biggest value in low is never bigger than the smallest in high. So the two halves stay sorted relative to each other.

After that move, high might have one too many. The if checks that. If high is bigger, it moves one value back to low. So low is always equal to high or has exactly one extra.

In find_median, if low has the extra number, its top is the median. We return -self.low[0] to undo the negation. Otherwise both halves are equal. So we average the two tops. The total count is even there, so the middle sits between the two tops.

⏱️ Time and Space Complexity

The sorting approach is simple but pays a big cost on every median call. The two-heap approach makes each add cost only O(log n), because each heap push and pop is O(log n). Reading the median is O(1), because the tops are always ready. So the whole thing stays fast even for a long stream.

Approach	Add Number	Find Median	Space
Sort every time	O(n log n)	O(1)	O(n)
Keep the list sorted	O(n)	O(1)	O(n)
Two heaps	O(log n)	O(1)	O(n)

Tip

The two-heap pattern shows up a lot. Any time you need the middle, or you need to balance a “small half” against a “large half”, reach for a max-heap and a min-heap together.

🧩 Key Takeaways

✅ A heap keeps the most important value at the top, and add or remove costs O(log n).
✅ A max-heap holds the smaller half. A min-heap holds the larger half.
✅ Keep the two halves balanced so their sizes never differ by more than one.
✅ The median is the top of the bigger heap, or the average of the two tops.
✅ Reading the median is O(1), because the tops are always ready.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Design Search Autocomplete System Next Kth Largest Element in a Stream

Find Median from Data Stream

Follow Us

Follow Us