Skip to main content

30. Find Median from Data Stream

hardAsked at Expedia

Maintain the running median of a live price stream — Expedia's dynamic-pricing team uses the two-heap pattern to track the real-time median fare across thousands of concurrent flight searches.

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

Problem

Design a data structure that supports adding integers from a data stream and finding the median of all elements so far. Implement the MedianFinder class with addNum(int num) and findMedian() methods. findMedian() returns the median as a double — if the total count is even, the median is the average of the two middle elements.

Constraints

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

Examples

Example 1

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

Explanation: After [1,2]: median = (1+2)/2 = 1.5. After [1,2,3]: median = 2.

Approaches

1. Sorted array (naive)

Keep elements in a sorted array. Insert in O(n) via binary search + shift. findMedian is O(1). Too slow for a high-frequency pricing stream.

Time
O(n) per addNum, O(1) 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;
    if (n % 2 === 1) return this.data[Math.floor(n / 2)];
    return (this.data[n / 2 - 1] + this.data[n / 2]) / 2;
  }
}

Tradeoff:

2. Two heaps (max-heap lower half, min-heap upper half)

Maintain a max-heap for the lower half and a min-heap for the upper half, balanced so they differ in size by at most 1. addNum is O(log n); findMedian is O(1).

Time
O(log n) per addNum, O(1) 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) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, 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 (upper half)
  }

  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.peek();
    return (-this.lo.peek() + this.hi.peek()) / 2;
  }
}

Tradeoff:

Expedia-specific tips

Expedia's hardest pricing interviews involve streaming data at scale. The two-heap approach is the expected answer — walk through the invariant: lo holds the lower half (inverted as a max-heap), hi holds the upper half (min-heap), and after every insertion we rebalance so lo is never smaller than hi. Their follow-up is typically 'what if 99% of values are in a known range?' — the answer is a bucketed counter that degrades to the heap only for outliers.

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

Practice these live with InterviewChamp.AI →