Solution: Find Median from Data Stream

Explore how to implement a MedianOfStream class that dynamically tracks and returns the median of integers using max and min heaps. Understand heap balancing techniques and analyze time and space complexities for efficient median calculation during coding interviews.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using heaps

Statement

Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, $O(1)$ , as the list grows. To do that, implement a class named MedianOfStream with the following functionality:

Constructor(): Initializes an instance of the class.
insertNum(int num): Adds a new integer num to the data structure.
findMedian(): Returns the median of all integers added so far.

Note: The median is the middle value in a sorted list of integers.
For an odd-sized list (e.g., $[4, 5, 6]$ ), the median is the middle element: $5$ .
For an even-sized list (e.g., $[2, 4, 6, 8]$ ), the median is the average of the two middle elements: $(4 + 6) / 2 = 5$ .

Constraints:

...