Dashboard
LC #295
Find Median from Data Stream
Pattern · ?AmazonGoogleMetaBloomberg
Problem
Design a data structure that supports adding numbers and finding the median at any time.
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.0
- Why
- After [1,2]: median = (1+2)/2 = 1.5. After [1,2,3]: median = 2
Spot the pattern
Which pattern cracks it?
Hints
One at a time