Skip to main content

24. Find Median from Data Stream

hardAsked at Nubank

Design a data structure supporting addNum and findMedian over a numeric stream; Nubank uses the two-heap split as an analog for running-quantile risk scoring over a card-auth firehose.

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

Problem

Design a MedianFinder that supports addNum(num) and findMedian(). After each insertion, findMedian must return the current median in better than linear time.

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(); addNum(3); findMedian()
Output
1.5, 2.0

Example 2

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

Approaches

1. Sorted-array binary insert

Binary-search for insertion index, then splice. findMedian is O(1) but addNum is O(n) due to shift.

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

Tradeoff:

2. Two heaps (max-low / min-high)

Keep a max-heap of the lower half and a min-heap of the upper half, balanced so their sizes differ by at most 1. Median is the top of the larger heap (or the average of both tops).

Time
addNum O(log n), findMedian O(1)
Space
O(n)
// Pseudocode — JS lacks a stdlib heap.
// low = max-heap, high = min-heap.
// addNum(x): if low empty or x <= low.top: low.push(x) else high.push(x).
//   Rebalance so |low| - |high| in {0, 1}.
// findMedian():
//   if low.size > high.size: return low.top.
//   return (low.top + high.top) / 2.

Tradeoff:

Nubank-specific tips

Nubank may ask you to extend this to a windowed median (last 1000 transactions); flag that an indexed multiset (or a deque-of-heaps with lazy deletes) is the right next step.

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

Practice these live with InterviewChamp.AI →