138. Find Median from Data Stream

Hard

Topics

Companies

Hint

Open Visualizer

Draw

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

Output: 1.5, 2.0

Explanation: After adding 1 and 2, the median is (1+2)/2 = 1.5. After adding 3, the median is 2.

Input: addNum(-1), addNum(-2), addNum(-3), findMedian(), addNum(-4), findMedian()

Output: -2.0, -2.5

Explanation: After adding -1, -2, -3, the median is -2. After adding -4, the median is (-2 + -3)/2 = -2.5

Time Complexity

O(log n)

Space Complexity

O(n)