24. Find Median from Data Stream

hardAsked at N26

Design a structure that supports adding numbers and querying the median in better than O(n) per op. N26 ports this to streaming the rolling median transaction value per customer for outlier scoring.

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

Problem

Implement MedianFinder with addNum(int num) and findMedian() returning the median of all elements added so far. Up to 5 * 10^4 operations.

Constraints

-10^5 <= num <= 10^5
There will be at least one element before findMedian is called
Total calls up to 5 * 10^4

Examples

Example 1

Input

addNum(1); addNum(2); findMedian();

Output

1.5

Example 2

Input

addNum(1); addNum(2); findMedian(); addNum(3); findMedian();

Output

1.5, 2.0

Approaches

1. Sorted array via splice

Binary-search insertion keeps the list sorted; median is the middle.

Time: O(n) per insert
Space: O(n)

// arr.push then sort, or binary-search-insert.
// 5*10^4 inserts at O(n) shift each = too slow.

Tradeoff:

2. Two heaps balance trick

Max-heap holds the smaller half; min-heap holds the larger half. Insert into one, push its top to the other to rebalance, and the median is the top of the larger heap (or average of both tops). Insert and query are O(log n).

Time: O(log n) per op
Space: O(n)

class MedianFinder {
  constructor() { this.lo = []; this.hi = []; }
  _push(h, v, cmp) { h.push(v); let i = h.length-1; while (i>0) { const p=(i-1)>>1; if (cmp(h[i],h[p])>=0) break; [h[i],h[p]]=[h[p],h[i]]; i=p; } }
  _pop(h, cmp) { const t = h[0]; const last = h.pop(); if (h.length) { h[0]=last; let i=0; for(;;){ let l=2*i+1,r=2*i+2,s=i; if(l<h.length&&cmp(h[l],h[s])<0)s=l; if(r<h.length&&cmp(h[r],h[s])<0)s=r; if(s===i)break; [h[s],h[i]]=[h[i],h[s]]; i=s; } } return t; }
  addNum(n) {
    this._push(this.lo, n, (a,b)=>b-a);
    this._push(this.hi, this._pop(this.lo, (a,b)=>b-a), (a,b)=>a-b);
    if (this.hi.length > this.lo.length)
      this._push(this.lo, this._pop(this.hi, (a,b)=>a-b), (a,b)=>b-a);
  }
  findMedian() {
    return this.lo.length > this.hi.length ? this.lo[0] : (this.lo[0] + this.hi[0]) / 2;
  }
}

Tradeoff:

N26-specific tips

N26 likes when you note that two-heap balance is exactly how their per-customer outlier scorer keeps a rolling median update-time bounded inside the streaming budget.

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

Practice these live with InterviewChamp.AI →