Find Median from Data Stream

1. Define the problem

Design a structure that supports adding integers one at a time from a data stream and finding the median of all values added so far, at any point. Given an array nums, return the median reported after each insertion , in order. Keep two heaps : a max-heap for the smaller half of the numbers and a min-heap for the larger half , kept balanced in size so the median sits at one or both roots.

Constraints

-10⁵ ≤ num ≤ 10⁵
The number of calls that add a number is in the range [1, 5 × 10⁴]

Example

Inputnums = [5, 15, 1, 3]

Output[5, 10, 5, 4]

Explanation After [5]: median 5. After [5, 15]: median (5+15)/2 = 10. After [1, 5, 15]: median 5. After [1, 3, 5, 15]: median (3+5)/2 = 4.

2. Know the words first

In plain terms

Two-heap median: A max-heap holds the smaller half of the values seen so far and a min-heap holds the larger half. Balanced in size, the median is always at one root (odd count) or the average of both roots (even count).

3. Visualize the solution

Two balanced heaps, median at the root(s)

smaller (max)5

larger (min)—

Statusinsert 5

First value: goes into the max-heap (smaller half). Median = 5.

What happens in this step

pushMax(lower, 5)  →  lower = [5]
upper = []

Only one value exists so far, sitting alone at the root of the smaller-half max-heap. Median = lower[0] = 5.

Step 1 of 4

Steps to visualize

Add each new value to the max-heap (smaller half) if it belongs there, otherwise the min-heap (larger half).
Rebalance: if one heap has more than one extra element, move its root to the other heap.
If the heaps are the same size, the median is the average of both roots.
If one heap has one more element, its root alone is the median.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two balanced heaps, median at the root(s)

smaller (max)5

larger (min)—

Statusinsert 5

First value: goes into the max-heap (smaller half). Median = 5.

What happens in this step

pushMax(lower, 5)  →  lower = [5]
upper = []

Only one value exists so far, sitting alone at the root of the smaller-half max-heap. Median = lower[0] = 5.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function medianStream(nums) {
  const lower = []; // max-heap: the smaller half
  const upper = []; // min-heap: the larger half

  function pushMax(heap, val) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent] < heap[i]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDownMax(heap) {
    let i = 0;
    const size = heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left] > heap[largest]) largest = left;
      if (right < size && heap[right] > heap[largest]) largest = right;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  }

  function popMax(heap) {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDownMax(heap);
    }
    return top;
  }

  function pushMin(heap, val) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent] > heap[i]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDownMin(heap) {
    let i = 0;
    const size = heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left] < heap[smallest]) smallest = left;
      if (right < size && heap[right] < heap[smallest]) smallest = right;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  }

  function popMin(heap) {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDownMin(heap);
    }
    return top;
  }

  const results = [];

  for (const num of nums) {
    if (lower.length === 0 || num <= lower[0]) {
      pushMax(lower, num);
    } else {
      pushMin(upper, num);
    }

    if (lower.length > upper.length + 1) {
      pushMin(upper, popMax(lower));
    } else if (upper.length > lower.length) {
      pushMax(lower, popMin(upper));
    }

    if (lower.length > upper.length) {
      results.push(lower[0]);
    } else {
      results.push((lower[0] + upper[0]) / 2);
    }
  }

  return results;
}

Time: O(log n) per insertion
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [5, 15, 1, 3]`	`[5, 10, 5, 4]`	example from the docstring
`nums = [7]`	`[7]`	smallest valid input, a single value
`nums = [2, 8]`	`[2, 5]`	exactly two values, median is their average
`nums = [10, 5, 1]`	`[10, 7.5, 5]`	values inserted in descending order, includes a fractional median
`nums = [4, 4, 4]`	`[4, 4, 4]`	every inserted value is identical
`nums = [-5, -1, -10, -2]`	`[-5, -3, -5, -3.5]`	negative numbers with multiple fractional medians

Find Median from Data Stream