Median of a Data Stream

Problem Description

Design a data structure that accepts a dynamic stream of integers and supports finding the median of all received numbers at any time.

The median is the middle value in an ordered integer list:

• If the size of the list is odd, the median is the middle element.
• If the size of the list is even, the median is the arithmetic mean of the two middle elements.

Implement the MedianFinder class:

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

    def add_num(self, num: int) -> None:
        """Inserts an integer into the data stream."""
        pass

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

Note on arithmetic safety: In typed systems or environments with fixed-width integers, adding two large middle numbers can cause integer overflow. Ensure your logic prevents overflow when calculating the mean.

Examples

Example 1

mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median())  # Output: 1.5
mf.add_num(3)
print(mf.find_median())  # Output: 2.0

Explanation:

• Stream: [1], median is 1.0.
• Stream: [1, 2], median is (1 + 2) / 2.0 = 1.5.
• Stream: [1, 2, 3], median is 2.0.

Example 2 (Large Values)

mf = MedianFinder()
mf.add_num(2147483647)
mf.add_num(2147483647)
print(mf.find_median())  # Output: 2147483647.0

Constraints

• -2^31 <= num <= 2^31 - 1
• Up to 100,000 total calls will be made to add_num and find_median.
• find_median() is guaranteed to be called only when at least one number has been added.
• Expected time complexity: O(log n) for add_num, O(1) for find_median.

Edge Cases to Consider

• Adding duplicates or negative numbers.
• Stream with both values near 2^31 - 1 or near -2^31 where a + b would overflow a signed 32-bit integer.
• Querying after single element insertions.