DSA problem
Find Median from Data Stream
The median is the middle value of a sorted list of numbers. If the list has an even number of elements, the median is the average of the two middle values. Implement the MedianFinder class that supports adding numbers to a data stream one at a time and returning the running median at any point.
A naive solution sorts the buffered numbers on every findMedian call, costing O(n log n) per query. A slightly better idea inserts each new number into a sorted array using binary search, which is O(log n) for the search but O(n) for the shift on insert. Neither is fast enough when the stream is long and queries are frequent.
The optimal design uses two heaps that together partition the seen numbers into two halves. A max-heap named low stores the smaller half (its top is the largest of that half), and a min-heap named high stores the larger half (its top is the smallest of that half). The invariant is len(low) ∈ {len(high), len(high) + 1}, so low can hold at most one extra element compared to high.
To add a number, push it onto low first, then move the top of low to high to keep them ordered, and finally rebalance by moving the top of high back to low if high has grown larger. To find the median, peek at the top of low when the total count is odd, or average the tops of both heaps when it is even. Each addNum runs in O(log n) and each findMedian runs in O(1).
Examples
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]][null,null,null,1.5,null,2.0]["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]][null,null,2.0,null,2.5]["MedianFinder","addNum","addNum","addNum","addNum","findMedian"]
[[],[5],[1],[3],[2],[]][null,null,null,null,null,2.5]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 addNum and findMedian.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.