Find Median from Data Stream

Intuition

The median only depends on the one or two values in the middle of the sorted order, so we never need the whole sequence sorted — we just need fast access to the middle. We keep the smaller half of the numbers in a max-heap whose root is the largest of the small values, and the larger half in a min-heap whose root is the smallest of the large values. If we keep the two halves balanced in size, those two roots straddle the median. When the total count is odd we let one heap hold the extra element and its root is the median; when it is even the median is the average of the two roots. Rebalancing after every insertion keeps both heaps within one element of each other.

Algorithm walkthrough

1. 1Maintain a max-heap `lower` for the smaller half and a min-heap `upper` for the larger half.
2. 2To add a number, first push it onto `lower`, then move `lower`'s root over to `upper` so every value in `lower` is <= every value in `upper`.
3. 3If `upper` now has more elements than `lower`, move `upper`'s root back to `lower` to restore balance.
4. 4This keeps the size difference at most one, with any extra element resting in `lower`.
5. 5For findMedian, if `lower` is larger, return its root; the total count is odd and that root is the middle value.
6. 6Otherwise the counts are equal, so return the average of `lower`'s root and `upper`'s root.

Implementation

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []  # max-heap (store negatives)
        self.upper = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lower, -num)
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def findMedian(self) -> float:
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])
        return (-self.lower[0] + self.upper[0]) / 2.0