#123

Median of an Integer Stream

hard

heap-priority-queuedesignsorting

Design a structure that ingests integers from a stream and can report the median of everything seen so far at any time. The median is the middle value of the sorted sequence; for an even count it is the average of the two middle values.

The structure supports two operations:

- "addNum" — add an integer num to the stream. Returns null. - "findMedian" — return the median of all integers added so far.

You are given the operations as two parallel arrays: operations[i] is the operation name and values[i] is its argument list ([num] for "addNum", [] for "findMedian"). Apply them in order and return an array holding each operation's return value (null for every "addNum").

For example ["addNum","addNum","findMedian","addNum","findMedian"] with [[1],[3],[],[2],[]] returns [null, null, 2, null, 2]: after adding 1 and 3 the median is (1 + 3) / 2 = 2; after also adding 2 the sorted stream is [1, 2, 3] with median 2.

"findMedian" is only called after at least one "addNum".

Example

Input: operations = ["addNum","addNum","findMedian","addNum","findMedian"], values = [[1],[3],[],[2],[]]

Output: [null,null,2,null,2]

Median of {1,3} is (1+3)/2 = 2; adding 2 gives {1,2,3} with median 2.

Constraints

1 <= operations.length <= 10^4
operations[i] is one of "addNum", "findMedian".
-10^5 <= num <= 10^5 for every "addNum".
findMedian is only called on a non-empty stream.

Intuition

The naïve design keeps every number in a list. addNum appends in O(1), but findMedian then has to sort the whole history and read the middle — O(n log n) on every query.

function runMedianOps(operations, values) {
  const nums = [];
  const result = [];
  for (let i = 0; i < operations.length; i++) {
    if (operations[i] === 'addNum') {
      nums.push(values[i][0]);            // O(1) add
      result.push(null);
    } else {                              // findMedian: sort, read the middle
      const sorted = [...nums].sort((a, b) => a - b);
      const n = sorted.length;
      const mid = n >> 1;
      result.push(n % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2);
    }
  }
  return result;
}

Brute force — store all, sort on each query: O(n log n) per findMedian.

Re-sorting the entire history on every findMedian is the waste — most of the data hasn't changed. Can we do better?

The key observation: the median only depends on the boundary between the smaller half and the larger half. Keep two heaps — a max-heap `low` for the smaller half (its top is the largest small value) and a min-heap `high` for the larger half (its top is the smallest large value) — balanced so low has the same size as high or exactly one more. This is the two-heaps technique from the Heaps intro.

Each addNum pushes into low, hands low's top to high (keeping every small value ≤ every large value), then rebalances if high outgrew low — a constant number of O(log n) heap ops. findMedian reads the tops in O(1): low's top when the count is odd, else the average of both tops.

Walking through the adds 5, 2, 8, 1 with a findMedian after each:

two heaps — low (max-heap, small half) | high (min-heap, large half)

add↓

add 5 → low{5} | high{} → median = 5

First value lands in low. Count is odd (1), so the median is low's top: 5.

add↓

add 2 → low{2} | high{5} → median = (2+5)/2 = 3.5

2 enters low, then low's top (5) moves to high. Even count: average the tops, 3.5.

add↓

add 8 → low{2,5} | high{8} → median = 5

8 enters low then high (8); high outgrew low, so high's top moves back. Odd count → low top 5.

add↓

add 1 → low{1,2} | high{5,8} → median = (2+5)/2 = 3.5

1 settles into the small half; the halves end balanced at 2 each. Even count → (2+5)/2 = 3.5.

sorted view {1,2 | 5,8} → boundary tops 2 and 5

The heaps partition the stream around the median; only the two boundary tops ever matter.

Optimization

Two heaps (max-heap low half, min-heap high half)

Split the stream into two halves around the median: a max-heap low holding the smaller half (its top is the largest of the small values) and a min-heap high holding the larger half (its top is the smallest of the large values). Keep them balanced so low has the same count as high or exactly one more.

To add a number, push to low, then move low's top to high (so the partition stays correct), then if high is now larger than low move high's top back. The median is low's top when the total count is odd, otherwise the average of both tops.

Each add does a constant number of O(log n) heap operations; findMedian reads the tops in O(1). So O(log n) per add and O(n) space.

function runMedianOps(operations, values) {
  // Generic binary heap; `less` defines the ordering so one class serves both halves.
  const makeHeap = (less) => {
    const data = [];
    const swap = (i, j) => { const t = data[i]; data[i] = data[j]; data[j] = t; };
    const up = (i) => {
      while (i > 0) {
        const parent = (i - 1) >> 1;
        if (!less(data[i], data[parent])) break;
        swap(parent, i);
        i = parent;
      }
    };
    const down = (i) => {
      const n = data.length;
      while (true) {
        let best = i;
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        if (l < n && less(data[l], data[best])) best = l;
        if (r < n && less(data[r], data[best])) best = r;
        if (best === i) break;
        swap(i, best);
        i = best;
      }
    };
    return {
      size: () => data.length,
      peek: () => data[0],
      push: (x) => { data.push(x); up(data.length - 1); },
      pop: () => {
        const top = data[0];
        const last = data.pop();
        if (data.length > 0) { data[0] = last; down(0); }
        return top;
      },
    };
  };

  const low = makeHeap((a, b) => a > b);  // max-heap: small half, top = largest small value
  const high = makeHeap((a, b) => a < b); // min-heap: large half, top = smallest large value

  const addNum = (num) => {
    low.push(num);              // always enters the small half first
    high.push(low.pop());       // hand its top to the large half to keep the partition sorted
    if (high.size() > low.size()) low.push(high.pop()); // rebalance so low >= high in count
  };
  const findMedian = () =>
    low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2;

  const result = [];
  for (let i = 0; i < operations.length; i++) {
    if (operations[i] === "addNum") {
      addNum(values[i][0]);
      result.push(null);
    } else {
      result.push(findMedian());
    }
  }
  return result;
}

Complexity analysis

Time complexity: O(log n) per addNum, O(1) per findMedian. Here's why:

addNum does a constant number of heap pushes/pops, each O(log n) on a heap of up to n elements.
findMedian only reads the one or two heap tops — O(1).

So a sequence of m operations over a stream of n numbers runs in O(m log n) — versus O(n log n) per query for the sort-every-time brute force.

Space complexity: O(n). Here's why:

Every number added lives in exactly one of the two heaps.

So the two heaps together hold all n stream values — O(n).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
operations = ["addNum","findMedian"], values = [[5],[]]	[null,5]	Single value — the median of one element is itself.
operations = ["addNum","addNum","findMedian"], values = [[1],[3],[]]	[null,null,2]	Even count: median is the average of the two middles, (1+3)/2 = 2.
operations = ["addNum","addNum","addNum","addNum","findMedian"], values = [[10],[20],[30],[40],[]]	[null,null,null,null,25]	Fractional/averaged median of an even count: (20+30)/2 = 25.
operations = ["addNum","addNum","findMedian"], values = [[-5],[5],[]]	[null,null,0]	Negatives and positives — median straddles zero: (-5+5)/2 = 0.
operations = ["addNum","findMedian","addNum","findMedian"], values = [[4],[],[2],[]]	[null,4,null,3]	Interleaved queries: median 4 (one element), then (2+4)/2 = 3.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor