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
Solve on LeetCode ↗