Questions
44 of 59
How do you find the median of a stream of numbers?
Difficulty: 5/10
Median of a Data Stream
Use two heaps: a max-heap containing the smaller half of values and a min-heap containing the larger half. Maintain their sizes so they differ by at most one. The median is the root of the larger heap or the average of both roots when their sizes are equal.
javascript
- 1
Insertion: O(log n).
- 2
Median query: O(1).
- 3
Space: O(n).
- 4
Max-heap stores lower half.
- 5
Min-heap stores upper half.
Follow-up Questions
- How do you rebalance the heaps?
- How would you handle integer overflow when averaging two values?