This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#295) before relying on it.

Find Median from Data Stream

An interactive visualization of how two heaps (a max-heap and a min-heap) maintain the running median as numbers stream in. Watch the heaps rebalance after every insertion.

Heap / Priority Queue LeetCode 295 ↗ Hard

The Problem

Design a data structure that supports the following two operations:

addNum(num) — Add an integer num from the data stream to the data structure.
findMedian() — Return the median of all elements so far.

The median is the middle value in an ordered list. If the list size is even, the median is the average of the two middle values.

Example: After adding [1, 2, 3], the median after each add is 1, 1.5, 2.

Interactive Visualization

Numbers (comma-separated)

Preset

Speed:

Input Stream

Two Heaps

Max-Heap (lo) — left half

empty

Median

—

Min-Heap (hi) — right half

empty

Code

import java.util.PriorityQueueclass MedianFinder {    private val lo = PriorityQueue<Int>(compareByDescending { it })    private val hi = PriorityQueue<Int>() // min-heap    fun addNum(num: Int) {        // max-heap        lo.add(num)        hi.add(lo.poll())        if (hi.size > lo.size) {            lo.add(hi.poll())        }    }    fun findMedian(): Double {        if (lo.size > hi.size) return lo.peek().toDouble()        return (lo.peek() + hi.peek()) / 2.0    }}

import heapqclass MedianFinder:    def __init__(self):        self.lo = []  # max-heap (negated)        self.hi = []  # min-heap    def addNum(self, num):        heapq.heappush(self.lo, -num)        heapq.heappush(self.hi, -heapq.heappop(self.lo))        if len(self.hi) > len(self.lo):            heapq.heappush(self.lo, -heapq.heappop(self.hi))    def findMedian(self):        if len(self.lo) > len(self.hi):            return -self.lo[0]        return (-self.lo[0] + self.hi[0]) / 2

Status & Log

Press Step or Play to begin.

How It Works

Key Insight

Keep two heaps: a max-heap (lo) storing the smaller half of the numbers, and a min-heap (hi) storing the larger half. The max-heap’s top is the largest element in the left half, and the min-heap’s top is the smallest in the right half. The median is always at the boundary between the two heaps.

The Algorithm

Push to max-heap: First, push the new number onto lo (the max-heap, stored with negated values in Python).
Rebalance to min-heap: Pop the max of lo and push it onto hi. This ensures the largest element from the left half moves to the right half if needed.
Size check: If hi has more elements than lo, pop the min of hi and push it back onto lo. This maintains the invariant that lo always has equal or one more element than hi.
Find median: If lo has more elements, the median is the top of lo. Otherwise, it is the average of the tops of both heaps.

Complexity

addNum O(log n)

findMedian O(1)

Space O(n)

Each addNum performs at most three heap operations (push/pop), each costing O(log n). Finding the median is a constant-time peek at the top of one or both heaps. All n elements are stored across the two heaps, so space is O(n).