Find Median from Data Stream
Support adding numbers and returning the median at any time.
Why does this pattern fit?
Restate the exact job
Support adding numbers and returning the median at any time.
Two heaps can keep the lower and upper halves balanced.
O(log n) add · O(1) median · O(n) space
Balancing sizes without preserving order can put values in the wrong half.
How to solve Find Median from Data Stream
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Support adding numbers and returning the median at any time.
Why Heaps & ordered selection fits
Two heaps can keep the lower and upper halves balanced.
State to maintain
Max-heap lower, min-heap upper, sizes differing by at most one.
Transition
Insert by value, rebalance, and read one top or the average of both tops.
Time and space
O(log n) add · O(1) median · O(n) space
Counterexample to the tempting mistake
Balancing sizes without preserving order can put values in the wrong half.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.