Find Median from Data Stream

PracticeNeetCode ↗LeetCode ↗

Design a data structure that accepts integers one at a time from a stream and can report the median of all numbers seen so far at any point, efficiently.

Example

Key Pointers

• The median only depends on the boundary between the lower and upper halves of the data — you don't need the numbers fully sorted, just split correctly.
• Keep two heaps: a max-heap for the smaller half, a min-heap for the larger half. Their tops sit right at the boundary.
• Rebalancing after every insert (so the two heaps never differ in size by more than one) keeps findMedian an O(1) lookup.

Step-by-Step Analysis

1. Maintain small, a max-heap (via negated values) for the lower half, and large, a min-heap for the upper half.
2. On addNum(val): push into small first, then move small's current max into large — this guarantees every value in large is ≥ every value in small.
3. If that leaves large bigger than small, move large's min back into small to restore the size balance.
4. On findMedian(): if the heaps are equal size, average their two tops; otherwise small is guaranteed to hold one extra element, so return its top directly.

Complexity

Time: O(log n) per addNum, O(1) per findMedian — Space: O(n)

Code

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (negated values) — lower half
        self.large = []  # min-heap — upper half

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))

        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 -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Code Explanation

How the solution above works, piece by piece.

1. small is a max-heap (values negated) for the lower half; large is a min-heap for the upper half.
2. addNum pushes into small, then moves small's largest into large. This guarantees every value in small ≤ every value in large.
3. If large now has more elements, move its smallest back, so small is always equal in size or one larger.
4. findMedian: with an odd total it's small's top; with an even total it's the average of both tops.
5. addNum is O(log n); findMedian is O(1).

Visual Walkthrough

Running addNum(1), addNum(2), findMedian(), addNum(3), findMedian():

Video Explanation

NeetCode — Find Median from Data Stream, LeetCode 295