Find Median from Data Stream
The key idea
Keep the lower half of the numbers in a max-heap and the upper half in a min-heap. The two heap tops sit right at the middle, so the median is read in O(1) while each insert stays O(log n). Keep the two heaps balanced in size as numbers arrive.
Problem
Design a data structure that supports adding integers from a data stream and reading the running median at any time.
The median is the middle value of an ordered list. If the list has an even number of values, the median is the average of the two middle values. For [2,3] the median is 2.5; for [1,2,3] it is 2.
Implement the MedianFinder class. addNum(num) adds the integer num from the stream into the structure, and findMedian() returns the median of all values added so far. Answers within 10^-5 of the true median are accepted.
Constraints
- -10^5 <= num <= 10^5
- There will be at least one element in the data structure before calling
findMedian. - At most 5 * 10^4 calls will be made to
addNumandfindMedian.
Examples
Input: addNum(1), addNum(2), findMedian()
Output: 1.5
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.0
Complexity
Time: O(log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM