Find Median from Data Stream
Problem
The MedianFinder class finds the median of a data stream.
Implement addNum(int num) and findMedian() returning the median of current elements.
If the count is even, the median is the mean of the two middle values.
Examples
Example 1
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.0
Constraints
- •
-10^5 <= num <= 10^5 - •
At most 5*10^4 calls to addNum and findMedian.
Hints
Hint 1
Two heaps: max-heap for the lower half, min-heap for the upper half, kept balanced in size so the median is always at or near the top of one (or both) heaps.
Hint 2
A simpler brute force keeps a single sorted list, inserting each new value at its correct position — findMedian() is trivial O(1), but the INSERTION itself costs O(n) due to shifting elements, unlike the two-heap approach's O(log n) for every operation.
Solutions
class MedianFinderBruteForce {
private List<Integer> sorted = new ArrayList<>();
public void addNum(int num) {
int pos = Collections.binarySearch(sorted, num);
if (pos < 0) pos = -(pos + 1);
sorted.add(pos, num); // insertion into an ArrayList at an arbitrary index is O(n) — the actual bottleneck
}
public double findMedian() {
int n = sorted.size();
if (n % 2 == 1) return sorted.get(n / 2);
return (sorted.get(n / 2 - 1) + sorted.get(n / 2)) / 2.0;
}
}Time: O(n) addNum, O(1) findMedian · Space: O(n)