Maintain the running median of a number stream as values arrive.

TL;DR: Hold two heaps: a max-heap for the lower half and a min-heap for the upper half, kept balanced in size (differing by at most one). The median is the top of the larger heap (odd count) or the mean of the two tops (even count). Every insert is O(log n) and reading the median is O(1). The trick is rebalancing after each insert.

How to approach it. Explain why the obvious approaches fall short: a sorted array costs O(n) per insert since every value shifts, and re-sorting on each arrival is worse. Name the two-heap structure and its invariant (lower-half max-heap, upper-half min-heap, sizes within one), then write it while being explicit about the insert-then-rebalance step.

A strong answer. Split the stream around the median. The smaller half lives in a max-heap, so its largest value, the median candidate, sits on top. The larger half lives in a min-heap with its smallest on top. Keep the two heaps balanced in size and the median falls straight out of the tops.

import heapq

class MedianStream:
    def __init__(self):
        self.lo = []   # max-heap (store negatives) -> lower half
        self.hi = []   # min-heap -> upper half

    def add(self, x: float):
        heapq.heappush(self.lo, -x)                  # tentatively to lower half
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # move its max to upper
        if len(self.hi) > len(self.lo):              # rebalance sizes
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]                       # odd count
        return (-self.lo[0] + self.hi[0]) / 2        # even count

The pattern that guarantees correctness: push to lo, immediately move lo's max into hi (this keeps every element of hi greater than or equal to every element of lo), then if hi grew larger, move its min back to lo. After every add, lo holds the same count as hi or one more, so the median is lo's top (odd count) or the average of both tops (even count). Python ships only a min-heap, so store negatives to fake a max-heap; getting that sign juggling right is where people slip.

Key takeaways

• Two heaps turn an O(n) sorted-insert into O(log n) insert and O(1) median read.
• The size invariant (lengths differ by at most one) is what makes the median a top, or an average of tops; rebalance after every insert or the heaps drift.
• heapq is min-only, so negate values for the max-heap and negate again on read.
• For sliding windows or arbitrary percentiles, reach for lazy deletion / SortedList or a sketch like t-digest.

What interviewers probe next.

• "Complexity?" O(log n) per insert (heap push/pop), O(1) to read the median, O(n) space. A sorted structure would be O(n) per insert.
• "Sliding-window median (last k)?" Harder: you must also remove the element leaving the window. Use lazy deletion with a hash map of to-remove elements, or a balanced BST / indexed structure (SortedList).
• "Why two heaps, not a balanced BST?" A BST also works (O(log n)) and handles deletion more naturally; two heaps are simpler when you only insert and query the middle.
• "Streaming percentiles, not just median?" Approximate sketches (t-digest, GK) for arbitrary quantiles at scale, trading exactness for bounded memory.

Common mistakes.

• A sorted list/array, giving O(n) inserts that will not scale.
• Forgetting to rebalance, so the heaps drift and the median is wrong.
• Sign errors emulating a max-heap with Python's min-heap.
• Mishandling the even/odd cases when reading the median.