Find Median From Data Stream
The problem
Support adding integers one at a time and finding the median of all values seen. Median queries occur only after at least one insertion; average the middle pair for even counts.
Example
Add 4, 1 → median 2.5; then add 7 → median 4
Need a hint?
Keep the smaller half and larger half separately.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Use a max-heap for the lower half and a min-heap for the upper half. Insert, move an out-of-order root across if necessary, and rebalance so lower has either equal size or one extra value. The median is lower’s root or the mean of both roots.
Complexity
O(log n) insertion, O(1) median lookup, and O(n) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.