258. Find Median from Data Stream
Integers arrive one at a time, and at any moment you may be asked for the median of everything that has arrived so far — the middle value once the numbers are sorted, or the average of the two middle values when the count is even.
Design a MedianFinder container with two operations:
add_num(num)— absorb the next integer from the stream.find_median()— return the median of all integers absorbed so far, as a number (it always ends in.0or.5).
The judge constructs one MedianFinder, feeds it a scripted sequence of operations, and prints each find_median result. Both operations should stay fast even after tens of thousands of insertions — re-sorting the whole collection on every query is the trap.
Example 1:
Input: add_num(1), add_num(2), find_median(), add_num(3), find_median()
Output: 1.5, then 2.0
Explanation: After inserting 1 and 2 the sorted stream is [1, 2], so the median is (1 + 2) / 2 = 1.5. After inserting 3 it is [1, 2, 3], whose middle value is 2.
Example 2:
Input: add_num(-1), find_median(), add_num(-2), find_median()
Output: -1.0, then -1.5
Explanation: With only -1 present the median is -1. After -2 arrives the sorted stream is [-2, -1] and the median is (-2 + -1) / 2 = -1.5.
Constraints:
- 1 ≤ q ≤ 5 * 10⁴
- -10⁵ ≤ x ≤ 10⁵
- find_median is only called after at least one add
- Because inputs are integers, every median ends in .0 or .5 — one decimal place is exact.
Hints:
Keeping the collection sorted makes the median a direct index lookup. A binary-search insertion keeps it sorted in O(log n) compares — but shifting elements to make room still costs O(n) per add.
Split the numbers into two halves: a max-heap holding the smaller half and a min-heap holding the larger half. The median only ever involves the tops of the two heaps.
Keep the heaps balanced so their sizes differ by at most one. Route each new number through one heap and rebalance: push onto the max-heap, move its top to the min-heap, and move back if the min-heap grows too big.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: add_num(1), add_num(2), find_median(), add_num(3), find_median()
Expected output: 1.5, 2.0