Find Median from Data Stream

Explore how to implement a MedianOfStream class that maintains a dynamic list of integers and returns the median in constant time. Learn to use heaps effectively to handle data stream inputs and calculate medians for both odd and even-sized data lists, helping you optimize solutions for dynamic data problems.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

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., ...