#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/heap-priority-queue/find-median-from-data-stream-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/heap-priority-queue/find-median-from-data-stream-implementation

Repovive

LeetCode 295 Find Median from Data Stream - Implementation - Heap / Priority Queue | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 295 Find Median from Data Stream - Implementation

The approach

Max-heap for smaller half, min-heap for larger half. Keep balanced.

class MedianFinder: def init(self): self.small = [] # max-heap (use negative) self.large = [] # min-heap

def addNum(self, num):
    heappush(self.small, -num)
    heappush(self.large, -heappop(self.small))
    if len(self.large) > len(self.small):
        heappush(self.small, -heappop(self.large))

def findMedian(self):
    if len(self.small) > len(self.large):
        return -self.small[0]
    return (-self.small[0] + self.large[0]) / 2

$O(\log n)$ add, $O(1)$ findMedian, $O(n)$ space.