295. Find Median from Data Stream

Q: Why two heaps instead of one?

One heap (min or max) gives you O(log n) extraction of the min OR max but not the middle. Two heaps split the data so the median is always at one of the two heap tops — O(1) query.

Q: Why the two-step rebalance instead of just pushing to the smaller heap?

Because pushing directly doesn't preserve the ordering invariant. The two-step (push to lo, transfer lo.top to hi, optionally transfer back) ensures every element in lo is <= every element in hi after every addNum.

hardAsked at Netflix

Design a data structure that supports adding numbers and querying the current median. Netflix asks this because streaming data is core to their business — they want the two-heaps solution where the max-heap holds the lower half and the min-heap holds the upper half.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Netflix loops.

Glassdoor (2026-Q1)— Netflix L4/L5 onsite reports cite Find Median from Data Stream as their go-to streaming hard.
Blind (2025-12)— Netflix SWE writeups describe the two-heaps invariant as the explicit signal.

Problem

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class: MedianFinder() initializes the MedianFinder object; void addNum(int num) adds the integer num from the data stream to the data structure; double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

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","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]

Output

[null,null,null,1.5,null,2.0]

Explanation: MedianFinder mf; mf.addNum(1); mf.addNum(2); mf.findMedian() returns 1.5; mf.addNum(3); mf.findMedian() returns 2.0.

Approaches

1. Sorted array via insertion

Maintain a sorted array. On addNum, binary-search to find the insertion point and splice. On findMedian, return the middle (or average of two middles).

Time: addNum O(n), findMedian O(1)
Space: O(n)

class MedianFinderSorted {
  constructor() { this.arr = []; }
  addNum(num) {
    let l = 0, r = this.arr.length;
    while (l < r) { const m = (l + r) >> 1; if (this.arr[m] < num) l = m + 1; else r = m; }
    this.arr.splice(l, 0, num);
  }
  findMedian() {
    const n = this.arr.length;
    if (n % 2 === 1) return this.arr[n >> 1];
    return (this.arr[n / 2 - 1] + this.arr[n / 2]) / 2;
  }
}

Tradeoff: Easy to write but addNum is O(n) due to the splice. At 5 * 10^4 calls that's 2.5 * 10^9 ops in the worst case — TLE.

2. Two heaps (optimal)

lo is a max-heap of the smaller half; hi is a min-heap of the larger half. Keep |lo| - |hi| in {0, 1}. The median is lo.top() (odd total) or (lo.top() + hi.top()) / 2 (even total).

Time: addNum O(log n), findMedian O(1)
Space: O(n)

class MaxHeap {
  constructor() { this.h = []; }
  push(v) { this.h.push(v); this._up(this.h.length - 1); }
  pop() { const top = this.h[0]; const end = this.h.pop(); if (this.h.length) { this.h[0] = end; this._down(0); } return top; }
  top() { return this.h[0]; }
  size() { return this.h.length; }
  _up(i) { while (i) { const p = (i - 1) >> 1; if (this.h[p] >= this.h[i]) break; [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; } }
  _down(i) { const n = this.h.length; while (true) { let l = 2 * i + 1, r = 2 * i + 2, best = i; if (l < n && this.h[l] > this.h[best]) best = l; if (r < n && this.h[r] > this.h[best]) best = r; if (best === i) break; [this.h[i], this.h[best]] = [this.h[best], this.h[i]]; i = best; } }
}
class MinHeap {
  constructor() { this.h = []; }
  push(v) { this.h.push(v); this._up(this.h.length - 1); }
  pop() { const top = this.h[0]; const end = this.h.pop(); if (this.h.length) { this.h[0] = end; this._down(0); } return top; }
  top() { return this.h[0]; }
  size() { return this.h.length; }
  _up(i) { while (i) { const p = (i - 1) >> 1; if (this.h[p] <= this.h[i]) break; [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; } }
  _down(i) { const n = this.h.length; while (true) { let l = 2 * i + 1, r = 2 * i + 2, best = i; if (l < n && this.h[l] < this.h[best]) best = l; if (r < n && this.h[r] < this.h[best]) best = r; if (best === i) break; [this.h[i], this.h[best]] = [this.h[best], this.h[i]]; i = best; } }
}
class MedianFinder {
  constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
  addNum(num) {
    this.lo.push(num);
    this.hi.push(this.lo.pop());
    if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
  }
  findMedian() {
    if (this.lo.size() > this.hi.size()) return this.lo.top();
    return (this.lo.top() + this.hi.top()) / 2;
  }
}

Tradeoff: O(log n) per addNum, O(1) per findMedian. The two-step rebalance (push to lo, transfer top to hi, then transfer back if hi is bigger) guarantees the size invariant after every addNum.

Netflix-specific tips

Netflix specifically grades the heap invariant statement: 'lo has size ceil(n/2), hi has size floor(n/2), every element in lo <= every element in hi.' Articulate the invariant BEFORE writing code. JavaScript has no built-in heap; either write your own (as above) or state that you'd use a library — Netflix interviewers accept 'I'll sketch the heap interface and skip the impl' if you describe it correctly.

Common mistakes

Pushing directly to whichever heap is smaller — fails the ordering invariant (lo elements could be larger than hi elements).
Forgetting the two-step rebalance — must push to lo, transfer lo's top to hi, then check if hi grew bigger.
Returning lo.top() when sizes are equal — should be the average of lo.top() and hi.top().

Follow-up questions

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

Sliding Window Median (LC 480) — median over a window that slides through the stream.
What if values were unbounded (e.g., timestamps)? (Heaps still work; sorted-array breaks.)
What if you needed the 90th percentile instead of the median? (Two heaps still work with a different size ratio.)

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 instead of one?

One heap (min or max) gives you O(log n) extraction of the min OR max but not the middle. Two heaps split the data so the median is always at one of the two heap tops — O(1) query.

Why the two-step rebalance instead of just pushing to the smaller heap?

Because pushing directly doesn't preserve the ordering invariant. The two-step (push to lo, transfer lo.top to hi, optionally transfer back) ensures every element in lo is <= every element in hi after every addNum.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →