Skip to main content

23. Find Median from Data Stream

hardAsked at Byju's

Design a streaming data structure that returns the running median.

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

Problem

The median is the middle value in an ordered integer list. If the size of the list is even, the median is the mean of the two middle values. Implement MedianFinder with addNum(num) to add an integer and findMedian() to return the current median.

Constraints

  • -10^5 <= num <= 10^5
  • Up to 5 * 10^4 addNum calls

Examples

Example 1

Input
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output
1.5, 2.0

Example 2

Input
addNum(4), addNum(2), findMedian()
Output
3.0

Approaches

1. Sorted insertion array

Maintain a sorted array; binary-search insertion point per add, then read the median index.

Time
O(n) per add
Space
O(n)
class MedianFinder{constructor(){this.a=[];}
  addNum(x){let l=0,r=this.a.length;while(l<r){const m=(l+r)>>1;this.a[m]<x?l=m+1:r=m;}this.a.splice(l,0,x);}
  findMedian(){const n=this.a.length;return n%2?this.a[(n-1)/2]:(this.a[n/2-1]+this.a[n/2])/2;}
}

Tradeoff:

2. Two heaps balance

Maintain a max-heap of the lower half and a min-heap of the upper half balanced in size. Median is the top of the larger heap or the average of both tops.

Time
O(log n) per add
Space
O(n)
class MinHeap{constructor(){this.h=[];}push(v){this.h.push(v);let i=this.h.length-1;while(i){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 t=this.h[0],l=this.h.pop();if(this.h.length){this.h[0]=l;let i=0;for(;;){const a=2*i+1,b=a+1;let m=i;if(a<this.h.length&&this.h[a]<this.h[m])m=a;if(b<this.h.length&&this.h[b]<this.h[m])m=b;if(m===i)break;[this.h[m],this.h[i]]=[this.h[i],this.h[m]];i=m;}}return t;}peek(){return this.h[0];}size(){return this.h.length;}}
class MaxHeap extends MinHeap{push(v){super.push(-v);}pop(){return -super.pop();}peek(){return -super.peek();}}
class MedianFinder{constructor(){this.lo=new MaxHeap();this.hi=new MinHeap();}
  addNum(x){this.lo.push(x);this.hi.push(this.lo.pop());if(this.hi.size()>this.lo.size())this.lo.push(this.hi.pop());}
  findMedian(){return this.lo.size()>this.hi.size()?this.lo.peek():(this.lo.peek()+this.hi.peek())/2;}
}

Tradeoff:

Byju's-specific tips

Byju's adaptive-learning engine reports rolling median learner scores per cohort, so map the two-heap design onto that runtime to win bonus signal.

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

Practice these live with InterviewChamp.AI →