Streaming Median
Latency dashboards do this every second: maintain the median of a stream without re-sorting everything per event. The classic two-heap trick — half the numbers below, half above, the median always at the boundary.
The problem
Given nums, a stream of numbers, return a list of the running median after each element arrives. The median of an odd-sized prefix is the middle value; of an even-sized prefix, the mean of the two middle values. Target O(log n) per element with two heaps: a max-heap holding the smaller half and a min-heap holding the larger half, rebalanced so their sizes differ by at most one.
nums = [2, 1, 3][2, 1.5, 2]nums = [1, 2, 3, 4][1, 1.5, 2, 2.5]nums = [5, 5, 5][5, 5, 5]- 1 ≤ len(nums)
- Even-sized prefix → mean of the two middle values (may be fractional).
- Aim for O(log n) per element — the two-heap invariant, not a re-sort.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement running_median(nums) → list of medians after each element, using a max-heap for the low half and a min-heap for the high half.
- Invariant: every element in the low half ≤ every element in the high half, and sizes differ by ≤ 1.
- Push each new number onto one heap, then rebalance by moving a root if sizes drift.
- Python has only a min-heap (heapq) — store negated values to simulate the max-heap.
- Median: odd count → root of the bigger heap; even → average of both roots.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.