295. Find Median from Data Stream

Practice Find Median from Data Stream for free on NudgeCode: Hard, Heap pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design a class that receives numbers one at a time and can report the median of everything seen so far. With an odd count the median is the middle value; with an even count it is the average of the two middle values.

• addNum(num) adds a number.
• findMedian() returns the current median.

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for calls that return nothing). Answers within 1e-5 are accepted.

Example

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
->  [null,null,null,1.5,null,2.0]

Constraints

• -10^5 <= num <= 10^5
• findMedian is only called after at least one addNum
• Up to 5 * 10^4 calls in total; aim for O(log n) per addNum