Median from Data Stream
MediumMax-heap for the low half, min-heap for the high
Problem
Return the running median of a stream of numbers after each insertion.
Keep a max-heap of the smaller half and a min-heap of the larger half; the tops give the median.
The idea
The two-heap structure keeps the middle of the data at the two roots, so the running median is available without ever sorting. Rebalancing after each insert is what maintains that invariant.
The trick
- Push, transfer the top across, then rebalance the sizes.
- Equal sizes mean averaging the two roots.
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 5,15,1,3 Values: 5, 15, 1, 3.
1same as find-median-from-data-stream (two heaps)Input
- array
- [5, 15, 1, 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.