Skip to main content

28. Find Median from Data Stream

hardAsked at Etsy

Maintain a running median over a stream of numbers — Etsy's pricing analytics team uses this dual-heap pattern to track the median listing price in real time as new items are added without re-sorting.

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

Problem

The MedianFinder class finds the median of a data stream. Implement: MedianFinder() initializes the object, addNum(num) adds an integer from the stream, and findMedian() returns the median of all elements so far. If the count is even, the median is the mean of the two middle elements.

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls to addNum and findMedian
  • findMedian is called at least once after at least one addNum call

Examples

Example 1

Input
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output
1.5, 2.0

Example 2

Input
addNum(6), findMedian(), addNum(10), findMedian(), addNum(2), findMedian(), addNum(6), findMedian()
Output
6.0, 8.0, 6.0, 6.0

Approaches

1. Sorted array (re-sort on each insert)

Maintain a sorted array. On each addNum, binary-search for insertion position and splice the element in. findMedian reads the middle element(s). O(n) per addNum due to splice shifting.

Time
O(n) per addNum, O(1) per findMedian
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;
    const mid = n >> 1;
    return n % 2 === 1 ? this.data[mid] : (this.data[mid - 1] + this.data[mid]) / 2;
  }
}

Tradeoff:

2. Two heaps (max-heap left, min-heap right)

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. The max-heap's top and min-heap's top are the two middle elements. On addNum, route the number to the correct heap and rebalance so sizes differ by at most 1. findMedian is O(1). JavaScript lacks a built-in heap, so implement a minimal binary heap.

Time
O(log n) per addNum, O(1) per findMedian
Space
O(n)
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      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;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length > 0) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i;
        const l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}

class MedianFinder {
  constructor() {
    this.lo = new MinHeap(); // max-heap via negation
    this.hi = new MinHeap(); // min-heap
  }

  addNum(num) {
    this.lo.push(-num); // push to max-heap (negate)
    this.hi.push(-this.lo.pop()); // balance: smallest of lo goes to hi
    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:

Etsy-specific tips

Etsy's data engineering team asks this to distinguish candidates who know heap internals from those who stop at the sorted-array approach. The key insight to state out loud: 'the median is always at the boundary between the two halves — I only need to track those two boundary values, not the whole sorted sequence.' Also discuss the negation trick for implementing a max-heap using a min-heap class. Expect a follow-up on how to handle large data sets that don't fit in memory (reservoir sampling or external sort).

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 Etsy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →