Skip to main content

24. Find Median from Data Stream

hardAsked at Baidu

Design a class that ingests integers one at a time and returns the median of all values seen so far in O(log n).

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

Problem

Design a data structure that supports addNum(num) to ingest integers from a stream and findMedian() to return the median of all elements so far. The median is the average of the two middle values for an even-sized stream.

Constraints

  • -10^5 <= num <= 10^5
  • Up to 5 * 10^4 calls
  • findMedian called only after at least one addNum

Examples

Example 1

Input
addNum(1); addNum(2); findMedian();
Output
1.5

Example 2

Input
addNum(3); findMedian();
Output
2.0

Approaches

1. Sorted array on every add

Insert into a sorted array via binary-search-find then splice; median is the middle.

Time
O(n) per addNum
Space
O(n)
// Splice cost dominates; will TLE on the 50k-call budget.

Tradeoff:

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

Lower half in a max-heap, upper half in a min-heap; keep sizes within 1. Median is the top of the bigger heap, or the average of the two tops if equal.

Time
O(log n) per addNum, O(1) findMedian
Space
O(n)
class MedianFinder {
  constructor() { this.lo = []; this.hi = []; }
  _pushLo(x) { this.lo.push(x); let i = this.lo.length - 1; while (i > 0) { const p = (i-1)>>1; if (this.lo[p] < this.lo[i]) { [this.lo[p], this.lo[i]] = [this.lo[i], this.lo[p]]; i = p; } else break; } }
  _popLo() { const top = this.lo[0], last = this.lo.pop(); if (this.lo.length) { this.lo[0] = last; let i = 0; for (;;) { const l = 2*i+1, r = 2*i+2; let b = i; if (l < this.lo.length && this.lo[l] > this.lo[b]) b = l; if (r < this.lo.length && this.lo[r] > this.lo[b]) b = r; if (b === i) break; [this.lo[b], this.lo[i]] = [this.lo[i], this.lo[b]]; i = b; } } return top; }
  _pushHi(x) { this.hi.push(x); let i = this.hi.length - 1; while (i > 0) { const p = (i-1)>>1; if (this.hi[p] > this.hi[i]) { [this.hi[p], this.hi[i]] = [this.hi[i], this.hi[p]]; i = p; } else break; } }
  _popHi() { const top = this.hi[0], last = this.hi.pop(); if (this.hi.length) { this.hi[0] = last; let i = 0; for (;;) { const l = 2*i+1, r = 2*i+2; let s = i; if (l < this.hi.length && this.hi[l] < this.hi[s]) s = l; if (r < this.hi.length && this.hi[r] < this.hi[s]) s = r; if (s === i) break; [this.hi[s], this.hi[i]] = [this.hi[i], this.hi[s]]; i = s; } } return top; }
  addNum(num) {
    if (!this.lo.length || num <= this.lo[0]) this._pushLo(num);
    else this._pushHi(num);
    if (this.lo.length > this.hi.length + 1) this._pushHi(this._popLo());
    else if (this.hi.length > this.lo.length) this._pushLo(this._popHi());
  }
  findMedian() {
    if (this.lo.length > this.hi.length) return this.lo[0];
    return (this.lo[0] + this.hi[0]) / 2;
  }
}

Tradeoff:

Baidu-specific tips

Baidu runs the two-heap pattern on rolling ad-ranking quality scores, so be ready to extend it to a fixed-window variant where you also evict expiring entries.

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

Practice these live with InterviewChamp.AI →