Skip to main content

23. Find Median from Data Stream

hardAsked at LINE

Support adding numbers to a stream and reporting the running median — LINE uses this to test two-heap thinking, the same shape as their median-latency dashboards for chat delivery.

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

Problem

Design a MedianFinder class that supports addNum(num) to add a number to the stream and findMedian() to return the median of all elements added so far. The median is the middle value if the count is odd, otherwise the mean of the two middle values.

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls total.
  • There will be at least one element before findMedian().

Examples

Example 1

Input
addNum(1); addNum(2); findMedian()
Output
1.5

Example 2

Input
addNum(1); addNum(2); addNum(3); findMedian()
Output
2.0

Approaches

1. Sorted insert

Keep a sorted array, insert via binary search, return the middle.

Time
O(n) per addNum
Space
O(n)
// arr.splice(bsearch(arr,num),0,num);
// findMedian -> arr[mid] or avg of two middles.

Tradeoff:

2. Two heaps

Maintain a max-heap of the lower half and a min-heap of the upper half. Keep their sizes within one of each other; the median is either the top of the larger heap, or the average of both tops when sizes are equal.

Time
O(log n) per addNum
Space
O(n)
// MaxHeap low, MinHeap high.
class MedianFinder {
  constructor() { this.low = new MaxHeap(); this.high = new MinHeap(); }
  addNum(num) {
    this.low.push(num);
    this.high.push(this.low.pop());
    if (this.high.size() > this.low.size()) this.low.push(this.high.pop());
  }
  findMedian() {
    if (this.low.size() > this.high.size()) return this.low.peek();
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

Tradeoff:

LINE-specific tips

At LINE, mention that the two-heap structure is the same one they use behind real-time median-latency tracking for sticker delivery — sticker-delivery framing wins.

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

Practice these live with InterviewChamp.AI →