How do you find the median of a stream of numbers?

Difficulty: 5/10

heap, order statistics, stream processing

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.

Scenario Questions

0-2 years experience

Follow-up Questions