This problem follows the Two Heaps pattern, commonly found in the Heap / Priority Queue category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Max-heap for lower half, min-heap for upper half. Balance sizes after each insert.
The two heaps partition the data at the median — the max-heap root is the largest of the smaller half, the min-heap root is the smallest of the larger half.
lo = [] # max-heap (negated)
hi = [] # min-heap
def addNum(num):
heappush(lo, -num)
heappush(hi, -heappop(lo))
if len(hi) > len(lo):
heappush(lo, -heappop(hi))
def findMedian():
if len(lo) > len(hi):
return -lo[0]
return (-lo[0] + hi[0]) / 2Practice Find Median from Data Stream and similar Heap / Priority Queue problems with flashcards. Build pattern recognition through active recall.
Practice this problem