Find Median from Data Stream

Heap
Hard

Approach

Diagrams

Analysis

Time

Space

from heapq import heapify, heappush, heappop


class MedianFinder:
    def __init__(self):
        self.median = None
        self.smallerNums = []
        self.biggerNums = []

        heapify(self.smallerNums)
        heapify(self.biggerNums)

    def addNum(self, num):
        if len(self.smallerNums) == 0 or num <= -self.smallerNums[0]:
            heappush(self.smallerNums, -num)

        else:
            heappush(self.biggerNums, num)

        self.rebalanceHeaps()
        self.updateMedian()

    def findMedian(self):
        return self.median

    def rebalanceHeaps(self):
        if len(self.smallerNums) - len(self.biggerNums) == 2:
            heappush(self.biggerNums, -heappop(self.smallerNums))

        elif len(self.biggerNums) - len(self.smallerNums) == 2:
            heappush(self.smallerNums, -heappop(self.biggerNums))

    def updateMedian(self):
        if len(self.smallerNums) == len(self.biggerNums):
            self.median = (self.biggerNums[0] - self.smallerNums[0]) / 2

        elif len(self.smallerNums) > len(self.biggerNums):
            self.median = -self.smallerNums[0]

        else:
            self.median = self.biggerNums[0]

Learn

#Min Heap

#Max Heap

Videos