Solution: Find Median from Data Stream

Explore how to design a data structure that dynamically tracks the median from an ongoing stream of integers using two heaps. Learn to implement a max-heap for smaller values and a min-heap for larger ones to efficiently insert numbers and compute the median in constant time. Understand the time and space complexity of this heap-based approach and how to maintain balance between the heaps for accurate median calculation.

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: