Two Heaps
LC #295Hard
Find Median from Data Stream
Two Heaps
AmazonGoogleMetaBloombergProblem
Design a data structure that supports adding numbers and finding the median at any time.
heapdesigndata-stream
Constraints
- ›-10⁵ ≤ num ≤ 10⁵
- ›At most 5 × 10⁴ calls to addNum and findMedian
- ›findMedian called only when at least one number has been added
Example
Input
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()Output
1.5, 2.0Why
After [1,2]: median = (1+2)/2 = 1.5. After [1,2,3]: median = 2