Streaming Median

Start from brute force

The obvious approach keeps every value seen so far and, after each arrival, sorts the prefix and reads the middle element, or averages the middle two. It is correct by the definition of the median. It costs O(n log n) per arrival, so O(n² log n) for the whole stream, and O(n) space. Keeping one list sorted with bisect.insort is better but still O(n²) overall: the binary search is O(log n), yet each insert shifts up to n elements. Either way the cost per event grows with the stream, which is exactly what a latency dashboard updating every second cannot afford.

The approach

The median depends only on the boundary between the lower and upper halves, so keep the halves in two heaps and never sort. The reference uses low, a max-heap of the smaller half (Python’s heapq is a min-heap, so it stores negated values and the max is -low[0]), and high, a min-heap of the larger half.

Two invariants hold after every arrival: every value in low is ≤ every value in high, and len(low) equals len(high) or exceeds it by one. A new x goes to low if low is empty or x <= -low[0], otherwise to high, which keeps the ordering. Then at most one root moves to restore the sizes: if low is two ahead its max moves to high, and if high is ahead its min moves to low. The median is -low[0] when low is larger, otherwise the mean of the two roots.

Walk through an example

Streaming [5, 15, 1, 3, 8] moves a root in both directions, at step 4 and again at step 5, and returns [5.0, 10.0, 5.0, 4.0, 5.0].

Complexity

Each arrival costs at most three heap operations, O(log n), and reading the median is O(1), so the stream costs O(n log n) time and O(n) space for the two heaps. Re-sorting after each arrival is O(n² log n) in total, and a single sorted list maintained with bisect.insort is O(n²), because each insert can shift up to n elements.

Edge cases to test

• One element: running_median([7]) returns [7.0]. An empty stream returns [], but reading a median from empty heaps raises, so a live API needs a guard.
• Values equal to the boundary go to low, because the test is x <= -low[0], and the rebalance still holds the sizes: [5, 5, 5] returns [5.0, 5.0, 5.0] and [1, 1, 2, 2] returns [1.0, 1.0, 1.0, 1.5].
• A decreasing stream sends every value to low and forces a move to high on every second arrival: [9, 7, 5, 3] returns [9.0, 8.0, 7.0, 6.0].
• Negative values work unchanged, since negation is only an encoding: [-3, -1, -2] returns [-3.0, -2.0, -2.0].
• Averages are floats: [0.1, 0.2] gives 0.15000000000000002 as its second median, and Python’s / turns large integers into floats too, so [10**17, 10**17 + 1] gives 1e+17 instead of the exact 100000000000000000.5. Use fractions.Fraction if exact medians matter.

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).

Follow-ups an interviewer asks next

How would you report the median of only the last k values?

Now values leave as well as arrive. Keep the two heaps plus a dictionary of pending deletions, discard a root when it is marked as deleted (lazy deletion), and track each heap’s live size for the balancing rule. Alternatively, keep one balanced sorted structure with O(log k) insert and delete. Either way each step costs O(log k).

What about the 99th percentile instead of the median?

The same idea works for any fixed quantile: size the heaps so low holds the bottom 99% and read the boundary root. For dashboards over huge streams, approximate sketches such as t-digest or KLL keep bounded memory and answer every quantile with a controlled error.

The values are integers from 0 to 100. Can you do better?

Yes. Keep 101 counters and the total n. Each insert is O(1), and the median comes from walking the counters until the running sum passes n/2, which is at most 101 steps, a constant. Latency histograms with fixed buckets answer percentile queries the same way.

The stream is spread across many servers. How do you get a global median?

Exact medians do not merge: each server’s median says little about the global one. Either send every value to one place, or have each server keep a mergeable summary, such as a t-digest, a KLL sketch or a histogram with shared bucket edges, and merge the summaries into an approximate global median.

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.

Reference solution

import heapq

def running_median(nums):
    low, high = [], []   # low: max-heap via negation; high: min-heap
    out = []
    for x in nums:
        if not low or x <= -low[0]:
            heapq.heappush(low, -x)
        else:
            heapq.heappush(high, x)
        if len(low) > len(high) + 1:
            heapq.heappush(high, -heapq.heappop(low))
        elif len(high) > len(low):
            heapq.heappush(low, -heapq.heappop(high))
        if len(low) > len(high):
            out.append(float(-low[0]))
        else:
            out.append((-low[0] + high[0]) / 2)
    return out


print(running_median([2, 1, 3]))   # -> [2.0, 1.5, 2.0]

function runningMedian(nums: number[]): number[] {
  // Simple array-backed heaps keep the code short; the invariant is what matters.
  const low: number[] = [];  // max at index 0 (stored negated)
  const high: number[] = []; // min at index 0
  const push = (h: number[], v: number) => {
    h.push(v);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  };
  const pop = (h: number[]): number => {
    const top = h[0];
    const last = h.pop() as number;
    if (h.length) {
      h[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < h.length && h[l] < h[s]) s = l;
        if (r < h.length && h[r] < h[s]) s = r;
        if (s === i) break;
        [h[s], h[i]] = [h[i], h[s]];
        i = s;
      }
    }
    return top;
  };
  const out: number[] = [];
  for (const x of nums) {
    if (low.length === 0 || x <= -low[0]) push(low, -x);
    else push(high, x);
    if (low.length > high.length + 1) push(high, -pop(low));
    else if (high.length > low.length) push(low, -pop(high));
    out.push(low.length > high.length ? -low[0] : (-low[0] + high[0]) / 2);
  }
  return out;
}

console.log(runningMedian([2, 1, 3]));   // -> [2, 1.5, 2]