Skip to main content

24. Find Median from Data Stream

hardAsked at Flipkart

Maintain the running median of a number stream with O(log n) inserts and O(1) lookups — Flipkart uses it for live latency dashboards during Big Billion Days sale-event spike handling.

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

Problem

Design a class that supports addNum(int) and findMedian() so the running median of all inserted values is available. addNum should be O(log n) and findMedian O(1).

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), findMedian(), addNum(-2), findMedian()
Output
-1.0, -1.5

Approaches

1. Sorted array

Keep all values in a sorted array; binary-search insert.

Time
O(n) per add
Space
O(n)
// insert into sorted array shifts O(n) — too slow under load

Tradeoff:

2. Two heaps

Maintain a max-heap of the lower half and a min-heap of the upper half, balanced to differ by at most one. The median is the top of the larger heap, or the mean of the two tops.

Time
O(log n) add, O(1) median
Space
O(n)
class MedianFinder {
  constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
  addNum(x) {
    if (this.lo.size() === 0 || x <= this.lo.peek()) this.lo.push(x);
    else this.hi.push(x);
    if (this.lo.size() > this.hi.size() + 1) this.hi.push(this.lo.pop());
    else 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:

Flipkart-specific tips

Flipkart panels reward the invariant call-out — lower half size equals upper half size, plus or minus one — and follow up on bucketed/quantile sketches for streams above their heap limits.

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

Practice these live with InterviewChamp.AI →