Maintain the Median of a Data Stream

Problem Statement

Design a data structure that reads a stream of integers one by one and returns the current median of all elements read so far after each insertion.

If the number of elements is odd, the median is the middle element in the sorted list. If the number of elements is even, the median is the average of the two middle elements.

Implement the MedianFinder class:

class MedianFinder:
    def __init__(self):
        """Initialize the data structure."""

    def add_num(self, num: int) -> None:
        """Adds an integer from the data stream to the data structure."""

    def find_median(self) -> float:
        """Returns the median of all elements so far."""

Constraints

• add_num will be called up to 50,000 times.
• find_median will be called up to 50,000 times.
• Integer values are within the range [-10^5, 10^5].

Examples

Example 1

MedianFinder mf = new MedianFinder();
mf.add_num(1);
mf.add_num(2);
mf.find_median(); // returns 1.5 ( (1+2)/2 )
mf.add_num(3);
mf.find_median(); // returns 2.0

Edge Cases

• Stream with a single element.
• Stream with duplicate elements.
• Stream where all elements are the same.