← Back to problems
Find Median from Data Stream
HardData StructuresDescription
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...