Heap / Priority Queue
LC #295Hard
Find Median from Data Stream
Heap / Priority Queue
AmazonGoogleMetaMicrosoftBloombergAppleProblem
Design a data structure that supports adding numbers and finding the median in O(log n) and O(1) respectively.
heaptwo-heapsdesign
Constraints
- ›-10⁵ ≤ num ≤ 10⁵
- ›At most 5×10⁴ calls to addNum and findMedian
- ›At least one number added before findMedian
Example
Input
addNum(1) → addNum(2) → findMedian() → addNum(3) → findMedian()Output
1.5, 2.0Why
After [1,2]: median=1.5. After [1,2,3]: median=2.