Running Median

01 · Question

Implement add(value) and median() for a stream of integers. The median is the middle value for odd size and the average of the two middle values for even size. Querying an empty stream returns None in Python or (0, false) in Go.

Example: after adding 5, 1, 9, 2, the successive medians are 5, 3, 5, 3.5.

02 · Analysis

The lower half is a max-heap and the upper half a min-heap. Insert relative to the upper root, then rebalance so the upper heap has the same size or one more item. Ordering across the halves plus the size rule places the median at their roots. In Python, negate lower-half values to simulate a max-heap. Add costs O(log n), lookup O(1), storage O(n). Median results use floating-point arithmetic; exact rational output would need a different return type.

03 · Solution

Reference solution

1import heapq
2
3class MedianTracker:
4    def __init__(self):
5        self.low = []
6        self.high = []
7
8    def add(self, value):
9        if not self.high or value >= self.high[0]:
10            heapq.heappush(self.high, value)
11        else:
12            heapq.heappush(self.low, -value)
13        if len(self.low) > len(self.high):
14            heapq.heappush(self.high, -heapq.heappop(self.low))
15        elif len(self.high) > len(self.low) + 1:
16            heapq.heappush(self.low, -heapq.heappop(self.high))
17
18    def median(self):
19        if not self.high:
20            return None
21        if len(self.high) == len(self.low):
22            return (self.high[0] - self.low[0]) / 2
23        return self.high[0]

Merge Sorted Streams