Hard — Heap | Data Stream | Two Heaps | Design

The Problem

Design a data structure that supports adding integers from a data stream and finding the median of all elements added so far in constant time.

Approach

Use two heaps to maintain balance: a max heap for smaller half of elements and min heap for larger half. Keep heaps balanced so median is either the top of max heap or average of both tops.

Time: O(log n) for addNum, O(1) for findMedian · Space: O(n)

Code

import heapq

class MedianFinder:
    def __init__(self):
        self.min_heap = []  # To store larger elements
        self.max_heap = []  # To store smaller elements

    def addNum(self, num: int) -> None:
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # Balance the heaps
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment