gitGood.dev
← Back to problems

Find Median from Data Stream

HardData Structures

Description

The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement a data structure that supports the following operations: - `addNum(num)` - adds an integer number from the data stream to the data structure. - `findMedian()` - returns the median of all elements so far. **Input format:** An array of commands where each command is either `["addNum", num]` or `["findMedian"]`. Return an array of results where `addNum` produces `null` and `findMedian` produces the current median.
Example 1
Input: operations = [["addNum",1],["addNum",2],["findMedian"],["addNum",3],["findMedian"]]
Output: [null,null,1.5,null,2]
Explanation: After adding 1 and 2, median is (1+2)/2 = 1.5. After adding 3, median is 2.

Constraints

- -10^5 <= num <= 10^5 - There will be at least one addNum before any findMedian call. - At most 5 * 10^4 calls total.
Loading editor...