Design a class MedianFinder that receives numbers one at a time and can report the median of everything added so far. addNum(num) adds a number and findMedian() returns the median: the middle value if the count is odd, or the average of the two middle values if it is even.
- -10^5 <= num <= 10^5
- findMedian is called only after at least one addNum
- At most 5 * 10^4 calls in total
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Keeping a sorted list and inserting with binary search still costs O(n) per insert because elements shift. Notice that the median only needs the boundary between the lower half and the upper half. Store the lower half in a max-heap (low) and the upper half in a min-heap (high). If low always has the same size as high or one more, the median is low's top (odd count) or the average of both tops (even count). Each insert is O(log n).
Algorithm
- Push the new number into
low(the max-heap). - Move
low's largest element intohigh, so every value inlowis at most every value inhigh. - If
highis now bigger thanlow, movehigh's smallest element back tolow. - For the median, return
low's top iflowis larger, else the average of both tops.
O(log n) per addNum, O(1) per findMedianSpace: O(n)class MedianFinder: def __init__(self): self.low = [] # max-heap (negated values), smaller half self.high = [] # min-heap, larger halfΒ def addNum(self, num: int) -> None: heapq.heappush(self.low, -num) # keep every low value <= every high value heapq.heappush(self.high, -heapq.heappop(self.low)) if len(self.high) > len(self.low): # low may hold one extra element heapq.heappush(self.low, -heapq.heappop(self.high))Β def findMedian(self) -> float: if len(self.low) > len(self.high): return float(-self.low[0]) return (-self.low[0] + self.high[0]) / 2.0