Find Median from Data Stream
HardTwo heaps facing each other
Problem
Design a structure that returns the median of all numbers seen so far after each addition.
Keep a max-heap of the smaller half and a min-heap of the larger half; the tops give the median.
The idea
Keep the smaller half in a max-heap and the larger half in a min-heap, rebalancing so their sizes differ by at most one. The median is then the top of the larger heap, or the average of both tops when the sizes are equal.
The trick
- Always push to one heap then move its top to the other, to keep the halves correct.
- Sizes must stay within one of each other.
- O(log n) per insertion, O(1) per median query.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — add 1,2,3 Values: 1, 2, 3.
1maxHeap low, minHeap high (balanced)2add: push, rebalance3median: top of larger, or average of topsInput
- array
- [1, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- stream = [5, 15, 1, 3]
- Output:
- [5, 10.0, 5, 4.0]
- Explanation:
- Running medians after each insert.
Example 2
- Input:
- stream = [1, 2, 3]
- Output:
- [1, 1.5, 2]
- Explanation:
- Medians 1, 1.5, 2.
Example 3
- Input:
- stream = [2]
- Output:
- [2]
- Explanation:
- One number is its own median.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.