Find Median from Data Stream

Explore how to implement a class that stores a dynamically changing list of integers and efficiently finds the median at any time. Learn to apply the heaps pattern to manage data streams and calculate medians in constant time. This lesson helps you develop a solution that supports insertion and median finding operations optimized for coding interviews.

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