Find Median from a Data Stream

Problem Statement

Design a data structure that supports adding integers from a data stream and finding the median of all elements seen so far.

Implement:

1. addNum(num) — Add an integer to the data structure
2. findMedian() — Return the median of all elements so far

The median is the middle value in a sorted list. If the count is even, the median is the average of the two middle values.

Constraints

• -10^5 <= num <= 10^5
• At most 5 * 10^4 calls to addNum and findMedian
• findMedian can be called at any point
• addNum should be efficient (better than re-sorting each time)

Example

addNum(1)
addNum(2)
findMedian()  → 1.5   // sorted: [1, 2], avg of middle two

addNum(3)
findMedian()  → 2     // sorted: [1, 2, 3], middle element

What the Interviewer Expects

1. Suboptimal first — mention sorting on every findMedian (O(n log n)) or insertion into sorted array (O(n) per add). Acknowledge these are slow.
2. Optimal: Two Heaps —
   • Max-heap for the lower half
   • Min-heap for the upper half
   • Keep sizes balanced (differ by at most 1)
3. addNum logic — add to appropriate heap, then rebalance.
4. findMedian — if equal sizes, average the two tops. Otherwise, the top of the larger heap.
5. Time: O(log n) per add, O(1) per findMedian.

Follow-ups

1. What if 99% of numbers are in the range [0, 100]? Can you optimize using buckets/counting?
2. What if numbers can also be removed from the stream?
3. What if you need a running percentile (e.g., 90th percentile) instead of median?
4. How would you handle this in a distributed system with the stream split across machines?