DSA AnimatorDSA animations
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).

How to solve Find Median from Data Stream

LeetCode 295 · Hard · Heap / Priority Queue · Pattern: Two Heaps

Why the obvious approach is slow

Keeping a sorted list makes each insertion O(n). Sorting again for every query is even slower. Two heaps give O(log n) insertion and O(1) median.

The key idea

Split the numbers into a lower half and an upper half. The lower half lives in a max heap, so its largest value is on top. The upper half lives in a min heap, so its smallest value is on top. Keep the sizes balanced, with the lower half allowed one extra number. Then the median is the top of the lower heap, or the average of both tops.

Remember

A max heap for the lower half, and a min heap for the upper half. Their tops meet in the middle.

Run the animation above on your own input, or watch the 1:60 video explanation of Find Median from Data Stream with a dry run and Java code.

More Heap / Priority Queue problems