Solution: Find Median from Data Stream

Statement ▼

Create a data structure that can store a list of integers that can change in size over time and find the median from this dynamically growing list in constant time, $O(1)$ .

Implement a class, MedianOfStream, which should support the following operations:

Constructor(): This initializes the object of this class, which in turn creates the max and the min heap.
Insert Num(num): This adds an integer, num, to the data structure.
Find Median(): This finds the median of all elements seen so far. If there are an even number of elements, return the average of the two middle values.

Constraints:

$-10^5 \leq$ num $\leq 10^5$ , where num is an integer received from the data stream.
There will be at least one element in the data structure before the median is computed.
At most, $500$ calls will be made to the function that calculates the median.

Problem

Submissions

Solution: Find Median from Data Stream

Statement ▼

Create a data structure that can store a list of integers that can change in size over time and find the median from this dynamically growing list in constant time, $O(1)$ .

Implement a class, MedianOfStream, which should support the following operations:

Constructor(): This initializes the object of this class, which in turn creates the max and the min heap.
Insert Num(num): This adds an integer, num, to the data structure.
Find Median(): This finds the median of all elements seen so far. If there are an even number of elements, return the average of the two middle values.

Constraints:

$-10^5 \leq$ num $\leq 10^5$ , where num is an integer received from the data stream.
There will be at least one element in the data structure before the median is computed.
At most, $500$ calls will be made to the function that calculates the median.