#257 Find Median in a Data Stream

Design a data structure that supports adding numbers and finding their median.

The median is:

• For odd number of integers: the middle value when sorted
• For even number of integers: average of the two middle values when sorted

Implement the MedianFinder class:

• MedianFinder() initializes the object
• addNum(num: number) adds an integer from the stream
• findMedian(): number returns the current median

Constraints:

• -100,000 ≤ num ≤ 100,000
• findMedian will only be called after adding at least one number
• At most 50,000 calls will be made to addNum and findMedian

Examples:

const medianFinder = new MedianFinder();
medianFinder.addNum(1);    // [1]

medianFinder.findMedian(); // returns 1.0

medianFinder.addNum(3);    // [1, 3]

medianFinder.findMedian(); // returns 2.0

medianFinder.addNum(2);    // [1, 2, 3]

medianFinder.findMedian(); // returns 2.0