295. Find Median from Data Stream

Q: Why two heaps instead of a sorted set?

JavaScript has no built-in sorted set / TreeMap, so you'd have to implement one anyway. Two heaps reuse standard heap code and give O(log n) addNum naturally.

Q: Is the lazy-deletion variant useful for the sliding-window follow-up?

Yes — for the window version, lazy deletion (mark stale entries and skip them on top) avoids implementing heap.remove(). It's a common follow-up trick.

hardAsked at Pinterest

Pinterest's metrics infrastructure tracks rolling medians for latency and engagement signals. Find Median from Data Stream asks you to support addNum and findMedian on an online stream — the two-heap pattern is the production answer.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

Glassdoor (2026-Q1)— Pinterest backend / infra onsite reports cite Find Median from Stream as the hard data-structure round.
LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list as one of the harder entries.

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 MedianFinder: void addNum(int num), double findMedian().

Constraints

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

Examples

Example 1

Input

MedianFinder mf; mf.addNum(1); mf.addNum(2); mf.findMedian(); mf.addNum(3); mf.findMedian();

Output

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

Approaches

1. Sorted array with insertion (brute force)

Maintain a sorted array. addNum uses binary search to find insertion point then splices. findMedian indexes the middle.

Time: O(n) per addNum (splice shifts), O(1) findMedian
Space: O(n)

class MedianFinderSorted {
  constructor() { this.a = []; }
  addNum(num) {
    let lo = 0, hi = this.a.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.a[mid] < num) lo = mid + 1; else hi = mid;
    }
    this.a.splice(lo, 0, num);
  }
  findMedian() {
    const n = this.a.length;
    return n % 2 ? this.a[(n - 1) >> 1] : (this.a[n / 2 - 1] + this.a[n / 2]) / 2;
  }
}

Tradeoff: addNum is O(n) because splice shifts. Mention it as the obvious starting point, then move to the heap solution.

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

Lower half in a max-heap, upper half in a min-heap. Keep |sizes| <= 1. Median is heap roots if sizes equal, else top of the larger heap.

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

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

class MinHeap {
  constructor() { this.a = []; }
  push(v) { this.a.push(v); this._up(this.a.length - 1); }
  pop() {
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length > 0) { this.a[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.a[0]; }
  size() { return this.a.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p] > this.a[i]) { [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; }
      else break;
    }
  }
  _down(i) {
    const n = this.a.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let best = i;
      if (l < n && this.a[l] < this.a[best]) best = l;
      if (r < n && this.a[r] < this.a[best]) best = r;
      if (best === i) break;
      [this.a[best], this.a[i]] = [this.a[i], this.a[best]];
      i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.lower = new MaxHeap(); // bottom half
    this.upper = new MinHeap(); // top half
  }
  addNum(num) {
    if (this.lower.size() === 0 || num <= this.lower.peek()) this.lower.push(num);
    else this.upper.push(num);
    // Rebalance so |sizes| <= 1
    if (this.lower.size() > this.upper.size() + 1) this.upper.push(this.lower.pop());
    else if (this.upper.size() > this.lower.size()) this.lower.push(this.upper.pop());
  }
  findMedian() {
    if (this.lower.size() === this.upper.size()) return (this.lower.peek() + this.upper.peek()) / 2;
    return this.lower.peek();
  }
}

Tradeoff: O(log n) addNum + O(1) findMedian. The two-heap invariant ('lower is a max-heap, upper is a min-heap, |sizes| <= 1') is the part to narrate. This is the production-shaped answer.

Pinterest-specific tips

Pinterest interviewers care most about the invariant statement. Before writing any code: 'I'll maintain a max-heap for the lower half and a min-heap for the upper half, kept within size 1 of each other. The median is either the max-heap root, the min-heap root, or their average.' Then write it. Skipping the invariant statement and jumping straight to code makes you look junior even if the code is correct.

Common mistakes

Allowing the heaps to drift by more than 1 — findMedian returns the wrong value.
Always pushing to the same heap regardless of value — destroys the 'lower half / upper half' invariant.
Returning an integer when even-count requires a float (Math.floor vs / 2).
Forgetting to rebalance after addNum — sizes stay valid for one or two calls then drift.

Follow-up questions

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

Sliding-window median (LeetCode 480) — window slides over the stream, supports removal.
Add a random-access getElement(k) — kth element of the current set.
Distributed median across N machines — partial-quantile estimation.
Percentile queries — generalize median to arbitrary p.

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 a sorted set?

JavaScript has no built-in sorted set / TreeMap, so you'd have to implement one anyway. Two heaps reuse standard heap code and give O(log n) addNum naturally.

Is the lazy-deletion variant useful for the sliding-window follow-up?

Yes — for the window version, lazy deletion (mark stale entries and skip them on top) avoids implementing heap.remove(). It's a common follow-up trick.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →