Find Median from Data Stream

Design a class that receives a stream of integers and can answer findMedian() at any point. The catch is real-time: each call must be fast, and the data arrives incrementally, so sorting from scratch on every query is out of the question.

The key insight: the median splits the stream into two halves. Keep the smaller half in a max-heap (so its largest element is on top) and the larger half in a min-heap (smallest on top). The median is then a function of just the two roots: the max-heap root when sizes are unequal, the average of both roots when they are equal. Insertion is O(log n) — push into one half, then rebalance so the sizes differ by at most one. Python's heapq is a min-heap, so the lower half stores negated values to simulate a max-heap.

Approach in steps:

1. addNum: push into the max-heap (lower half); if the halves are unbalanced or out of order, move one element across.
2. Keep len(lower) == len(upper) or len(lower) == len(upper) + 1.
3. findMedian: return -lower[0] if lower is longer, else (-lower[0] + upper[0]) / 2.

import heapq
 
class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap via negation
        self.hi = []  # min-heap
 
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        if self.lo and self.hi and -self.lo[0] > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
 
    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Time is O(log n) per addNum, O(1) per findMedian; space is O(n) total.

Trickiest edge case: the first element — self.lo is empty and both halves are balanced, so the machine must not touch an empty heap. Negation also breaks if values overflow, but Python ints are unbounded, so it is safe here.