Skip to main content

23. Find Median from Data Stream

hardAsked at Riot Games

Design a structure that returns the median of a streaming sequence — Riot uses two-heap streaming medians to track rolling Elo/Glicko percentile windows.

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

Problem

Implement MedianFinder supporting addNum(num) to insert a value and findMedian() to return the current median. addNum should run in better than linear time and findMedian must return the exact median.

Constraints

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

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 insertion

Insert each value into a sorted array using binary-search insert and return the middle element(s).

Time
O(n)
Space
O(n)
// On addNum, binary-search and splice into a sorted array
// findMedian = middle index or average of two
// O(n) insertion dominates at high volume

Tradeoff:

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

Keep a max-heap for the lower half and a min-heap for the upper half; balance sizes after every insert so the median is either the top of one heap or the average of both tops. Same dual-heap structure Riot uses to track rolling Elo/Glicko medians across matchmaking pools without resorting on every match.

Time
O(log n) per addNum, O(1) findMedian
Space
O(n)
class Heap {
  constructor(cmp){this.h=[]; this.cmp=cmp;}
  push(v){this.h.push(v); this._up(this.h.length-1);}
  pop(){const t=this.h[0]; const e=this.h.pop(); if(this.h.length){this.h[0]=e; this._down(0);} return t;}
  peek(){return this.h[0];}
  size(){return this.h.length;}
  _up(i){while(i>0){const p=(i-1)>>1; if(this.cmp(this.h[p], this.h[i])<=0) break; [this.h[p],this.h[i]]=[this.h[i],this.h[p]]; i=p;}}
  _down(i){const n=this.h.length; while(true){let l=2*i+1,r=l+1,s=i; if(l<n&&this.cmp(this.h[l],this.h[s])<0) s=l; if(r<n&&this.cmp(this.h[r],this.h[s])<0) s=r; if(s===i) break; [this.h[s],this.h[i]]=[this.h[i],this.h[s]]; i=s;}}
}
class MedianFinder {
  constructor(){
    this.lower = new Heap((a,b)=>b-a); // max-heap
    this.upper = new Heap((a,b)=>a-b); // min-heap
  }
  addNum(num){
    if (!this.lower.size() || num <= this.lower.peek()) this.lower.push(num);
    else this.upper.push(num);
    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();
    return (this.lower.peek() + this.upper.peek()) / 2;
  }
}

Tradeoff:

Riot Games-specific tips

Riot expects you to design the two-heap rebalance invariant explicitly — the same logic their matchmaking service uses to keep rolling Elo/Glicko percentile windows accurate under streaming match results.

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

Practice these live with InterviewChamp.AI →