CODING CHALLENGE · N°21

Streaming Median

Medium Data StructuresHeapsSystems

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.

EXAMPLE 1

Input nums = [2, 1, 3]

Output [2, 1.5, 2]

median after each arrival

EXAMPLE 2

Input nums = [1, 2, 3, 4]

Output [1, 1.5, 2, 2.5]

even prefixes average the middle two

EXAMPLE 3

Input nums = [5, 5, 5]

Output [5, 5, 5]

duplicates are fine

CONSTRAINTS

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.

SOLVE IT YOURSELF

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.

YOUR TASK

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.

HINTS — 4 IDEAS

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.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Keep two heaps: a max-heap for the lower half of the values and a min-heap for the upper half. On each insert, place the value and rebalance so the heap sizes differ by at most one. The median is then the top of the larger heap, or the average of the two tops when the halves are equal — all without ever re-sorting.

Complexity

Time O(log n) per insert, O(1) to read the median; space O(n).

Common mistakes

Re-sorting the whole stream on each query — O(n log n) instead of O(log n) incremental.
Letting the two heaps drift out of balance, so the tops no longer straddle the median.
Getting a heap’s ordering direction backwards (lower half must be a max-heap).

Where this shows up

The two-heap running median powers real-time percentile and latency monitoring, moving-median smoothing, and any “median so far” over a stream you cannot re-scan. The balance-two-structures idea generalizes to maintaining running quantiles online.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Caching & Performance