090. Running Median

Why this mechanism works

Split the observations into a lower half and an upper half. A max-oriented heap exposes the largest lower value; a min-heap exposes the smallest upper value. Maintain the lower half with either equal size or one extra element so the median is always at the heap roots.

State and boundaries

lower stores negated lower-half values. upper stores upper-half values. Every lower value is <= every upper value; len(lower) is len(upper) or one larger.

Protocol

1. Insert into the appropriate half by comparing with the lower maximum.
2. Rebalance by moving one root if necessary.
3. Read the lower root for odd size.
4. Average the two roots for even size.

Visualization

lower (max side) <= upper (min side)
[1,2] | [3,4] -> median (2+3)/2
[1,2,3] | [4,5] -> median 3

Python implementation

import heapq

def running_medians(values):
    lower, upper, output = [], [], []
    for value in values:
        if not lower or value <= -lower[0]:
            heapq.heappush(lower, -value)
        else:
            heapq.heappush(upper, value)
        if len(lower) > len(upper) + 1:
            heapq.heappush(upper, -heapq.heappop(lower))
        elif len(upper) > len(lower):
            heapq.heappush(lower, -heapq.heappop(upper))
        if len(lower) == len(upper):
            output.append((-lower[0] + upper[0]) / 2)
        else:
            output.append(float(-lower[0]))
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 running_medians: lower, upper, output = [], [], []
values=[1, 2, 3, 4]; lower=[]; upper=[]; output=[]

L5 running_medians: for value in values:
values=[1, 2, 3, 4]; lower=[]; upper=[]; output=[]; value=1

L7 running_medians: heapq.heappush(lower, -value)
values=[1, 2, 3, 4]; lower=[-1]; upper=[]; output=[]; value=1

L17 running_medians: output.append(float(-lower[0]))
values=[1, 2, 3, 4]; lower=[-1]; upper=[]; output=[1.0]; value=1

L5 running_medians: for value in values:
values=[1, 2, 3, 4]; lower=[-1]; upper=[]; output=[1.0]; value=2

L9 running_medians: heapq.heappush(upper, value)
values=[1, 2, 3, 4]; lower=[-1]; upper=[2]; output=[1.0]; value=2

L15 running_medians: output.append((-lower[0] + upper[0]) / 2)
values=[1, 2, 3, 4]; lower=[-1]; upper=[2]; output=[1.0, 1.5]; value=2

L5 running_medians: for value in values:
values=[1, 2, 3, 4]; lower=[-1]; upper=[2]; output=[1.0, 1.5]; value=3

... 2 intermediate state changes omitted ...

L17 running_medians: output.append(float(-lower[0]))
values=[1, 2, 3, 4]; lower=[-2, -1]; upper=[3]; output=[1.0, 1.5, 2.0]; value=3

L5 running_medians: for value in values:
values=[1, 2, 3, 4]; lower=[-2, -1]; upper=[3]; output=[1.0, 1.5, 2.0]; value=4

L9 running_medians: heapq.heappush(upper, value)
values=[1, 2, 3, 4]; lower=[-2, -1]; upper=[3, 4]; output=[1.0, 1.5, 2.0]; value=4

L15 running_medians: output.append((-lower[0] + upper[0]) / 2)
values=[1, 2, 3, 4]; lower=[-2, -1]; upper=[3, 4]; output=[1.0, 1.5, 2.0, 2.5]; value=4

L4 running_medians: lower, upper, output = [], [], []
values=[5, 5, 5]; lower=[]; upper=[]; output=[]

L5 running_medians: for value in values:
values=[5, 5, 5]; lower=[]; upper=[]; output=[]; value=5

L7 running_medians: heapq.heappush(lower, -value)
values=[5, 5, 5]; lower=[-5]; upper=[]; output=[]; value=5

L17 running_medians: output.append(float(-lower[0]))
values=[5, 5, 5]; lower=[-5]; upper=[]; output=[5.0]; value=5

L7 running_medians: heapq.heappush(lower, -value)
values=[5, 5, 5]; lower=[-5, -5]; upper=[]; output=[5.0]; value=5

L11 running_medians: heapq.heappush(upper, -heapq.heappop(lower))
values=[5, 5, 5]; lower=[-5]; upper=[5]; output=[5.0]; value=5

L15 running_medians: output.append((-lower[0] + upper[0]) / 2)
values=[5, 5, 5]; lower=[-5]; upper=[5]; output=[5.0, 5.0]; value=5

L7 running_medians: heapq.heappush(lower, -value)
values=[5, 5, 5]; lower=[-5, -5]; upper=[5]; output=[5.0, 5.0]; value=5

L17 running_medians: output.append(float(-lower[0]))
values=[5, 5, 5]; lower=[-5, -5]; upper=[5]; output=[5.0, 5.0, 5.0]; value=5

Why the solution is correct

Insertion into the correct side preserves ordering; transferring a boundary root during rebalancing preserves that order too. The size invariant positions the middle element or middle pair exactly at the exposed roots, so each reported median is correct.

Time and space

O(n log n) total time and O(n) storage; each insertion uses O(log n) heap work.

Common mistakes

Balancing sizes without preserving cross-heap order is insufficient. Negated lower values must be converted back when reporting or transferring.

Reasoning card

Transfer exercise

Support a fixed-size sliding median. Identify why expired values require deletion support or lazy removal in both heaps.