Skip to main content

295. Find Median from Data Stream

hardAsked at Google

Maintain the median of a stream of numbers with O(log n) addNum and O(1) findMedian. Google asks this to test whether you reach for two heaps (max-heap of lower half + min-heap of upper half) and can articulate the size-balance invariant.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the data-structure design round.
  • Blind (2025-11)— Recurring Google senior IC interview problem.

Problem

The median is the middle value in an ordered integer list. Implement the MedianFinder class: addNum(num) - adds a number from the stream, findMedian() - returns the median of all elements so far.

Constraints

  • -10^5 <= num <= 10^5
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 10^4 calls will be made to addNum and findMedian.

Examples

Example 1

Input
MedianFinder(); addNum(1); addNum(2); findMedian(); addNum(3); findMedian()
Output
[null,null,null,1.5,null,2.0]

Approaches

1. Sorted array with binary-search insert

Maintain a sorted array. Binary-search the insertion point, splice the new value.

Time
O(n) addNum, O(1) findMedian
Space
O(n)
class MedianFinderSorted {
  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;
    return n % 2 ? this.data[n >> 1] : (this.data[n / 2 - 1] + this.data[n / 2]) / 2;
  }
}

Tradeoff: Splice is O(n) — fails the spec's expected O(log n) for addNum. Mention only to anchor.

2. Two heaps (optimal)

Max-heap for the lower half + min-heap for the upper half. Maintain |sizes| <= 1. Median is heap top (odd total) or average of both tops (even total).

Time
O(log n) addNum, O(1) findMedian
Space
O(n)
class MaxHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() {
    if (!this.data.length) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.data[0]; }
  size() { return this.data.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p] >= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _down(i) {
    while (true) {
      const l = 2*i+1, r = 2*i+2;
      let best = i;
      if (l < this.data.length && this.data[l] > this.data[best]) best = l;
      if (r < this.data.length && this.data[r] > this.data[best]) best = r;
      if (best === i) break;
      [this.data[best], this.data[i]] = [this.data[i], this.data[best]];
      i = best;
    }
  }
}

class MinHeap extends MaxHeap {
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _down(i) {
    while (true) {
      const l = 2*i+1, r = 2*i+2;
      let best = i;
      if (l < this.data.length && this.data[l] < this.data[best]) best = l;
      if (r < this.data.length && this.data[r] < this.data[best]) best = r;
      if (best === i) break;
      [this.data[best], this.data[i]] = [this.data[i], this.data[best]];
      i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.lo = new MaxHeap(); // lower half
    this.hi = new MinHeap(); // upper half
  }
  addNum(num) {
    this.lo.push(num);
    this.hi.push(this.lo.pop()); // funnel through to keep ordering
    if (this.hi.size() > this.lo.size()) {
      this.lo.push(this.hi.pop());
    }
  }
  findMedian() {
    if (this.lo.size() > this.hi.size()) return this.lo.peek();
    return (this.lo.peek() + this.hi.peek()) / 2;
  }
}

Tradeoff: Two heaps split the stream. Funneling every new number through both heaps guarantees correct partitioning. Size-balance invariant: |lo| - |hi| in {0, 1}.

Google-specific tips

Google interviewers grade this on whether you can articulate the two-heap invariants BEFORE writing code: (1) lo is a max-heap holding the smaller half, hi is a min-heap holding the larger half; (2) lo.size() - hi.size() is always 0 or 1; (3) every element in lo is <= every element in hi. If you can state all three, the implementation falls out.

Common mistakes

  • Forgetting to funnel new numbers through both heaps — adding directly to one breaks the ordering invariant.
  • Maintaining the size-balance the wrong direction (allowing |hi| > |lo|).
  • Off-by-one when computing the median for even total size.

Follow-up questions

An interviewer at Google may pivot to one of these next:

  • What if you only cared about a sliding window of the last k numbers?
  • What if you needed the k-th smallest, not just the median?
  • How would you handle 100B numbers (out-of-core)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why two heaps and not one balanced BST?

A balanced BST would work (O(log n) per insert) but heaps are simpler to implement and have better constants. The two-heap split is also conceptually clearer: 'lower half' and 'upper half.'

Why funnel through both heaps?

Funneling guarantees that the new number ends up in the correct half. If lo has 3 elements and hi has 3 elements, blindly pushing to lo (without funneling) might place a large number in lo, breaking the invariant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →