Skip to content
Onsite
9 / 9

Find Median from Data Stream

HardP2Coding

Design a structure that supports a stream of integers and reports the median of everything added so far. The median is the middle value of the sorted data; if the count is even it is the mean of the two middle values.

  • MedianFinder() creates an empty structure.
  • addNum(num) adds an integer to the data.
  • findMedian() returns the median of all elements so far. It is only called when at least one element has been added.

Answers within 10^-5 of the true value would be accepted in the original problem; here the tests use values that are exact in floating point.

Example 1

Input
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]
Output
[null,null,null,1.5,null,2]

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls in total
  • findMedian is called only after at least one addNum

Hints

Run checks the 2 visible tests, Submit all 5.