Find Median from Data Stream
Problem
Build a structure that accepts integers one at a time through addNum and can report the median of everything added so far through findMedian. With an even count the median is the mean of the two middle values.
Examples
Constraints
- • -10^5 <= num <= 10^5
- • findMedian is called only after at least one addNum
- • Up to 5 * 10^4 calls
Hints & approach
Hint 1
Keeping a sorted list costs O(n) per insert.
Hint 2
You only need the largest of the lower half and the smallest of the upper half.
Hint 3
Use a max-heap for the lower half and a min-heap for the upper half, and keep their sizes balanced.
Approachtry the hints first
Store the smaller half in a max-heap and the larger half in a min-heap, with the max-heap allowed one extra element. To add, push onto the max-heap, then move its top to the min-heap so every lower value stays <= every upper value; if the min-heap is now larger, move its top back. The median is the max-heap top when the total is odd, or the average of both tops when it is even. Each insert is O(log n) and each query O(1).
Time O(log n) add, O(1) median · Space O(n)