Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Tags: Heap

Try It!

Discussion

Video

Solution

import heapq

class MedianFinder:

    def __init__(self):
        self.lower = []
        self.greater = []

    def addNum(self, num: int) -> None:
        if len(self.lower) == len(self.greater):
            heapq.heappush(self.greater, num)
            greater_min = heapq.heappop(self.greater)
            heapq.heappush(self.lower, -greater_min)
        else:
            heapq.heappush(self.lower, -num)
            lower_max = heapq.heappop(self.lower)
            heapq.heappush(self.greater, -lower_max)

    def findMedian(self) -> float:
        if len(self.lower) == len(self.greater):
            return (-self.lower[0] + self.greater[0]) / 2
        else:
            return -self.lower[0]

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()