Skip to main content

24. Find Median from Data Stream

hardAsked at Instacart

Maintain a running median as numbers stream in — Instacart applies this pattern to real-time delivery-time tracking where the median ETA must update on every new completed order without a full re-sort.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The MedianFinder class should support two operations: addNum(num) adds an integer num from the data stream, and findMedian() returns the median of all elements seen so far. If the total count is even, the median is the average of the two middle values.

Constraints

  • -10^5 <= num <= 10^5
  • findMedian() will always be called after at least one addNum()
  • At most 5 * 10^4 calls total to addNum and findMedian

Examples

Example 1

Input
MedianFinder mf; mf.addNum(1); mf.addNum(2); mf.findMedian(); mf.addNum(3); mf.findMedian();
Output
1.5, 2.0

Explanation: After [1,2] the median is 1.5; after [1,2,3] it is 2.0.

Approaches

1. Sorted array insertion

Keep all numbers in a sorted array; binary search to insert each new number and read the middle.

Time
O(n) per add, O(1) find
Space
O(n)
class MedianFinder {
  constructor() {
    this.data = [];
  }

  addNum(num) {
    let lo = 0, hi = this.data.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.data[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    this.data.splice(lo, 0, num);
  }

  findMedian() {
    const n = this.data.length;
    if (n % 2 === 1) return this.data[n >> 1];
    return (this.data[n / 2 - 1] + this.data[n / 2]) / 2;
  }
}

Tradeoff:

2. Two heaps (max-heap lo + min-heap hi)

Maintain a max-heap of the lower half and a min-heap of the upper half, balanced to within 1 element. The median is either the top of the larger heap or the average of both tops.

Time
O(log n) per add, O(1) find
Space
O(n)
// Note: JS lacks a built-in heap; we simulate with sorted arrays here to keep code runnable.
// In an interview, declare MinHeap/MaxHeap as helpers or agree on a library.
class MedianFinder {
  constructor() {
    this.lo = []; // max-heap (lower half) — stored negated for min-heap simulation
    this.hi = []; // min-heap (upper half)
  }

  _pushMax(heap, val) {
    heap.push(-val);
    heap.sort((a, b) => a - b);
  }
  _popMax(heap) { return -heap.shift(); }
  _peekMax(heap) { return -heap[0]; }

  _pushMin(heap, val) {
    heap.push(val);
    heap.sort((a, b) => a - b);
  }
  _popMin(heap) { return heap.shift(); }
  _peekMin(heap) { return heap[0]; }

  addNum(num) {
    this._pushMax(this.lo, num);
    // Balance: ensure lo top <= hi top
    if (this.hi.length && this._peekMax(this.lo) > this._peekMin(this.hi)) {
      this._pushMin(this.hi, this._popMax(this.lo));
    }
    // Rebalance sizes
    if (this.lo.length > this.hi.length + 1) {
      this._pushMin(this.hi, this._popMax(this.lo));
    } else if (this.hi.length > this.lo.length) {
      this._pushMax(this.lo, this._popMin(this.hi));
    }
  }

  findMedian() {
    if (this.lo.length > this.hi.length) return this._peekMax(this.lo);
    return (this._peekMax(this.lo) + this._peekMin(this.hi)) / 2;
  }
}

Tradeoff:

Instacart-specific tips

Instacart tracks real-time delivery ETA distributions and surfaces median delivery time on the ops dashboard. The two-heap answer is the expected solution — interviewers want you to explain the invariant (lo.size >= hi.size, lo.max <= hi.min) before writing a single line of code. In JS you'd declare a proper heap class; call that out rather than sorting arrays in production.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find Median from Data Stream and other Instacart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →