Track the Median of a Stream

Problem Statement

Design a data structure MedianTracker that accepts a stream of integers and provides the current median at any point in time.

Implement the following methods:

• add_num(num: int) -> None: Adds an integer from the stream to the data structure.
• find_median() -> float: Returns the median of all elements added so far. If the number of elements is even, return the average of the two middle elements.

Constraints

• -10^6 <= num <= 10^6
• add_num and find_median must be called at most 5 * 10^4 times each.
• The time complexity for add_num should be O(log n) and find_median should be O(1).

Examples

# Example 1
tracker = MedianTracker()
tracker.add_num(1)
tracker.add_num(2)
tracker.find_median() # Returns 1.5 ( (1+2)/2 )
tracker.add_num(3)
tracker.find_median() # Returns 2.0

Edge Cases

• Stream is empty when find_median is called (return 0 or handle as needed).
• Stream contains negative numbers.
• Stream contains duplicate numbers.

Implementation Template

class MedianTracker:
    def __init__(self):
        pass

    def add_num(self, num: int) -> None:
        pass

    def find_median(self) -> float:
        pass