← Back to DSA Animator
Find Median from Data Stream LC #295 Hard Heap · Two Heaps
Problem

The median is the middle value in an ordered integer list. If the list size is even, the median is the mean of the two middle values. Implement MedianFinder: addNum(int num) adds an integer from the data stream, findMedian() returns the median of all elements so far.

Example 1
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: [1.5, 2.0]
Explanation: After [1,2]: median = 1.5. After [1,2,3]: median = 2.0
Example 2
Input: addNum(6), addNum(3), findMedian(), addNum(7), addNum(2), findMedian()
Output: [4.5, 4.5]
Explanation: After [3,6]: median = 4.5. After [2,3,6,7]: median = 4.5
Constraints: −105 ≤ num ≤ 105  |  At most 5·104 calls to addNum and findMedian
Try Examples
Custom:
Approach
Two Heaps: maxHeap holds lower half, minHeap holds upper half
Keep sizes balanced (differ by at most 1). Median = peek of larger heap OR average of both tops
Heap Towers
Max Heap (lower half) 0
empty
—
Min Heap (upper half) 0
empty
median = ?
—
Variables
num
—
maxH.peek
—
minH.peek
—
n (count)
0
median
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
⚖
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init: maxH = max-heap (lower half), minH = min-heap (upper half)
2
Push num to maxH, then push maxH.poll() to minH
3
Rebalance: if minH.size > maxH.size, move minH.poll() to maxH
4
findMedian: if maxH.size > minH.size → maxH.peek(); else → avg of tops
addNum
O(log n)
findMedian
O(1)
Space
O(n)
Why Two Heaps Work

We keep the stream split at the median boundary: maxH (max-heap) holds the lower half so its top is the largest small value, and minH (min-heap) holds the upper half so its top is the smallest large value. By ensuring sizes stay balanced (equal or maxH one larger), the median is always instantly available at the heap tops — no scanning needed. Each addNum is O(log n), findMedian is O(1).