Find Median from Data Stream
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian
Problem
Design a data structure that supports addNum(int num) and findMedian() in O(log n) and O(1) time respectively. This is a classic system design and algorithm hybrid question.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Apple | Hard | View all Apple questions → |
| Netflix | Hard | View all Netflix questions → |
| Uber | Hard | View all Uber questions → |
| Atlassian | Hard | View all Atlassian questions → |
How to Think About It
Use two heaps: a max-heap for the lower half and a min-heap for the upper half.
Balance invariant: the max-heap can have at most one more element than the min-heap. This ensures the median is always at the top of one or both heaps.
On addNum: push to one heap, then rebalance. If the max of lower half > min of upper half, swap them.
Median: if sizes differ, return the max-heap top (extra element). Otherwise, average both tops.
Visual walkthrough for [5, 15, 1, 3]:
addNum(5): lo=[5], hi=[]. Balanced.
addNum(15): push to lo → lo=[15,5]. push 15 to hi → lo=[5], hi=[15]. Balanced.
addNum(1): push to lo → lo=[5,1]. Max of lo (5) > min of hi (15)? No. Balanced.
addNum(3): push to lo → lo=[5,3,1]. Push max to hi → lo=[3,1], hi=[5,15].
findMedian(): sizes equal → (3+5)/2 = 4.
Edge cases: single element (that element), even/odd count, negative numbers.
Optimal Approach
class MedianFinder:
lo = [] (max-heap, store negatives)
hi = [] (min-heap)
addNum(num):
push -num to lo
push -heappop(lo) to hi (move max of lo to hi)
if len(hi) > len(lo): push -heappop(hi) to lo (rebalance)
findMedian():
if len(lo) > len(hi): return -lo[0]
return (-lo[0] + hi[0]) / 2
Time: O(log n) add, O(1) find. Space: O(n).
What Trips People Up in Real Interviews
Using a sorted list. Insert is O(n), not O(log n). Use two heaps for O(log n) insert.
Confusing "median" with "mean." The median is the middle value (odd count) or average of two middle values (even count).
Not maintaining the balance invariant. The max-heap can have at most one more element than the min-heap.
Forgetting to handle the case where heaps are equal size. The average of both tops is the median.
Pushing to the wrong heap first. Always push to lo (max-heap), then move the max of lo to hi (min-heap), then rebalance. Pushing to hi first can break the balance invariant.
Solution Code
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (inverted)
self.hi = [] # min-heap
def addNum(self, num):
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo))
if len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def findMedian(self):
if len(self.lo) > len(self.hi):
return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2Frequently Asked Questions
What is the Find Median from Data Stream problem?
Design a data structure that supports addNum(int num) and findMedian() in `O(log n)` and `O(1)` time respectively. This is a classic system design and algorithm hybrid question.
How do you solve Find Median from Data Stream?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find Median from Data Stream?
Find Median from Data Stream is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian. It is a hard difficulty problem.
What are common mistakes on Find Median from Data Stream?
- Using a sorted list. Insert is `O(n)`, not `O(log n)`. Use two heaps for `O(log n)` insert.
- Confusing "median" with "mean." The median is the middle value (odd count) or average of two middle values (even count).
- Not maintaining the balance invariant. The `max-heap` can have at most one more element than the `min-heap`.
- Forgetting to handle the case where heaps are equal size. The average of both tops is the median.
- Pushing to the wrong heap first. Always push to lo (`max-heap`), then move the max of lo to hi (`min-heap`), then rebalance. Pushing to hi first can break the balance invariant.