LeetCode #295 Hard

Find Median from Data Stream

Support addNum and findMedian as numbers stream in, both fast.

heapdesigntwo-heaps

02

Intuition

💡

Keep the lower half in a max-heap and the upper half in a min-heap. The median is at the roots — no scanning. Each insert goes into one heap and rebalances at most one element across, so both roots always face the middle.

03

Approach

1

Two heaps face each other

lo (max-heap) holds the smaller half, hi (min-heap) the larger. Invariant: every lo element ≤ every hi element, sizes differ by ≤ 1.

2

Insert then rebalance

Push into lo, move lo's max to hi (guaranteeing the ordering invariant), then if hi outgrew lo, move hi's min back. Two heap ops, done.

3

Median from the roots

Odd count → lo's root (lo is the bigger heap). Even → average of both roots. O(1).

04

Solution & live demo

python

▶1import heapq
▶2 
▶3class MedianFinder:
▶4    def __init__(self):
▶5        self.lo = []   # max-heap (negated)
▶6        self.hi = []   # min-heap
▶7 
▶8    def addNum(self, num):
▶9        heapq.heappush(self.lo, -num)
▶10        heapq.heappush(self.hi, -heapq.heappop(self.lo))
▶11        if len(self.hi) > len(self.lo):
▶12            heapq.heappush(self.lo, -heapq.heappop(self.hi))
▶13 
▶14    def findMedian(self):
▶15        if len(self.lo) > len(self.hi):
▶16            return -self.lo[0]
▶17        return (-self.lo[0] + self.hi[0]) / 2

05

Edge cases

Values arriving in sorted order

Rebalancing keeps halves even regardless of arrival order.

Duplicates crossing the median

Invariant is ≤ so equal values may sit on both sides — fine.

06

Complexity

Time

O(log n) add, O(1) median

Space

O(n)

Two heaps, sizes within 1.