Big O Practice: Find Median Stream

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (store negated)
        self.hi = []  # min-heap

    def add_num(self, num):
        heapq.heappush(self.lo, -num)
        top_lo = -heapq.heappop(self.lo)
        heapq.heappush(self.hi, top_lo)
        if len(self.hi) > len(self.lo):
            top_hi = heapq.heappop(self.hi)
            heapq.heappush(self.lo, -top_hi)

    def find_median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Variables

• n - number of elements added so far

Explanation

`addNum` does a constant number of heap pushes/pops, each **O(log n)** - so per-add time is **O(log n)**. `findMedian` only peeks both heap tops in **O(1)**. The two heaps together hold all `n` elements seen so far, giving **O(n)** total space.

More Big O practice problems · Today's daily problem