Skip to main content

22. Find Median from Data Stream

hardAsked at Redis

Maintain a running median over a stream of numbers; Redis interviewers love it because two-heap balancing mirrors how Redis Streams hold per-consumer-group offsets.

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

Problem

Implement MedianFinder with addNum(num) and findMedian() returning the median of all numbers added so far. Both operations should be efficient under stream-rate workloads.

Constraints

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

Examples

Example 1

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

Example 2

Input
addNum(3); findMedian()
Output
2.0

Approaches

1. Sorted insertion

Keep a sorted array; insert each num at its sorted position.

Time
O(n) per add, O(1) median
Space
O(n)
// Binary-search insertion index then splice in.

Tradeoff:

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

Push small half onto max-heap, larger half onto min-heap. Re-balance so |sizes| <= 1. Median is heap top or average of tops. Same pattern as Redis ZSET-backed dual-leaderboards.

Time
O(log n) per add, O(1) median
Space
O(n)
class MedianFinder {
  constructor() {
    this.low = new MaxHeap();
    this.high = new MinHeap();
  }
  addNum(n) {
    this.low.push(n);
    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:

Redis-specific tips

Redis interviewers reward you for mapping the two-heap design to two ZSETs (low/high) and discussing how ZRANGEBYRANK keeps median lookup O(1) at the cost of double the memory.

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

Practice these live with InterviewChamp.AI →