hard

Find Median from Data Stream

Design a structure that receives integers one at a time and can report the median of all values received so far at any moment. For an even count the median is the mean of the two middle values.

Constraints

-10^5 ≤ num ≤ 10^5
At most 5 · 10^4 calls
findMedian is called only after at least one add

Examples

in: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()

out: 1.5, 2.0

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.