# LeetCode 295: Find Median From Data Stream — Step-by-Step Visual Trace

**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

```python
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

> **[Open interactive visualization](https://tracelit.dev/app?trace=0295_find-median-from-data-stream)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0295_find-median-from-data-stream) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*