← DSA Atlas
Dedicated problem page · #295

Find Median from Data Stream

HardHeap and Priority QueueTwo balanced heapsTwo heaps (max-heap + min-heap)
Solve on LeetCode ↗
295
HardHeap and Priority QueueTwo heaps (max-heap + min-heap)Two balanced heaps

Find Median from Data Stream

Design a data structure that supports adding integers from a data stream and querying the median of all values seen so far. Implement addNum(num) to insert a value and findMedian() to return the current median (average of the two middle values when the count is even).

Open official problem prompt ↗
In plain English

Maintain the running median of every number seen so far, answering each median query in constant time no matter how large the stream grows.

Picture it like this

Picture a see-saw. The left seat holds the smaller half of the numbers with the biggest of them at the pivot; the right seat holds the larger half with the smallest at the pivot. As long as the seats stay balanced in count, the median is whatever sits right at the pivot point.

Example
Input
addNum(1); addNum(2); findMedian(); addNum(3); findMedian()
Output
1.5 then 2.0
Why
After 1 and 2 the median is (1+2)/2 = 1.5; after adding 3 the sorted stream is [1,2,3] with median 2.
Constraints
-10^5 <= num <= 10^5There will be at least one element before findMedian is calledUp to 5 * 10^4 calls to addNum and findMedian
Pattern lesson

See the pattern, then code

Two balanced heaps
Recognition clue

Repeatedly querying the middle of a growing, unsorted stream signals splitting the data into a lower half and an upper half kept in balance.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. Keep the smaller half in a max-heap and the larger half in a min-heap. The two roots straddle the middle, so the median is one root or the average of both — available in O(1) after O(log n) inserts.

New words, made simpleKnow these before the algorithm
Max-heap
A heap whose largest element is at the root; simulated in Python by negating values in a min-heap.
Median
The middle value of an ordered set, or the average of the two middle values when the count is even.
Rebalance
Shifting one element between heaps so their sizes differ by at most one.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Sort on every query

Far too slow when queries are frequent.

Store all numbers and sort before each findMedian.

Time O(n log n) per querySpace O(n)
Insertion into sorted list

Query is O(1) but the shift on insert is linear, too slow at scale.

Keep a sorted list and binary-search the insertion point.

Time O(n) per insert (shifting)Space O(n)
Best choiceTwo balanced heaps

Best trade-off; both operations stay fast for the whole stream.

Split values into a max-heap lower half and min-heap upper half, kept balanced.

Time O(log n) insert, O(1) querySpace O(n)
The rule we keep true

Invariant

Every value in the max-heap is <= every value in the min-heap, and the max-heap size equals the min-heap size or is exactly one larger.

Why this is correct

Reasoning

The push-then-transfer step guarantees the largest of the lower half never exceeds the smallest of the upper half, so the heaps hold the true lower and upper halves. The size rule pins the middle element(s) to the roots, making the median a direct read.

The algorithm in three movesSay these aloud before coding
1Push the new number into the max-heap (lower half)

add 1: small=[1] large=[]

2Move that heap's largest into the min-heap to keep order between halves

add 2: small=[1] large=[2] -> median (1+2)/2=1.5

3Rebalance so the max-heap has equal size or one extra

add 3: small=[2,1] large=[3] -> median 2

4Median is the max-heap root, or the average of both roots when sizes are equal

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
1 · Read1
2 · AskWhere does 1 go?
3 · Update statepush to small then move to large then rebalance back: small=[1] large=[]
4 · ResultLower half holds 1.
Key takeaway

Lower half (max-heap) and upper half (min-heap) with roots meeting at the median.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-6Two heaps

    small is a max-heap (values negated) for the lower half; large is a min-heap for the upper half.

  2. 2
    Lines 9-10Push and hand off

    Insert into the lower half, then move its maximum to the upper half so the two halves stay correctly ordered.

  3. 3
    Lines 11-12Rebalance

    If the upper half grew larger, move its minimum back so small is never smaller than large.

  4. 4
    Lines 14-17Read the median

    An odd count leaves the extra element at small's root; an even count averages the two roots.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single element (odd count, median is that element)
  • All identical values
  • Negative numbers mixed with positives
  • Long strictly increasing or strictly decreasing streams, which stress rebalancing
!

Common beginner mistakes

  • Forgetting to negate when pushing to or reading from the max-heap
  • Skipping the transfer step and just comparing sizes, which lets a large lower-half value outrank the upper half
  • Integer division for the even case — the median can be a .5 fraction, so divide by 2.0
  • Allowing size difference to exceed one, which puts the wrong element at the root
Check your understanding

Why push a new number into the lower half first and immediately move its max to the upper half, instead of choosing a heap by comparison?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word#703Kth Largest Element in a StreamFixed-size min-heap (bounded top-k)