Median of a running stream of integers
Filed under Amazon
Free read 1 of 3Confirm the number of calls, how frequent each operation is, duplicates, negative numbers and whether values lie in a bounded range.
The question
Design a data structure that receives a continuous stream of integers and can return the median of all numbers seen so far at any time. Provide add(num) and median(). If the count is even, the median is the average of the two middle values.
Constraints
- Values are integers within the 32-bit range
- add and median may be called many times in any order
Examples
- Input
- add(1), add(2), median(), add(3), median()
- Output
- 1.5, then 2
- Why
- After [1,2] the median is 1.5, after [1,2,3] it is 2.
Approach
Confirm the number of calls, how frequent each operation is, duplicates, negative numbers and whether values lie in a bounded range.
Keep a list, sort on every query: O(n log n) per median. Or insert into a sorted list with bisect: O(n) insert, O(1) median.
Keep a max-heap for the smaller half and a min-heap for the larger half, balanced so sizes differ by at most one. The median is the top of the larger heap or the average of both tops. add is O(log n), median O(1).
The interviewer in the report preferred a tree approach. Use a balanced BST with subtree sizes (order-statistic tree) to find the k-th element in O(log n), which also supports deletions and sliding-window medians. Edge cases: first element, duplicates, even counts.
Solution
O(log n) add, O(1) median, O(n) space
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (stored as negatives)
self.hi = [] # min-heap
def add(self, num):
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # move largest of lo to hi
if len(self.hi) > len(self.lo): # keep lo >= hi in size
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def median(self):
if len(self.lo) > len(self.hi):
return float(-self.lo[0])
return (-self.lo[0] + self.hi[0]) / 2
Tips
- What they are testing: Whether you can maintain an invariant between two structures, and know the heap approach and its balanced-tree alternative.
- Common mistake: Re-sorting on every query, or forgetting to rebalance the heaps so the median is read from the wrong top.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.