Problem
Design a data structure that supports the following operations:addNum(num) adds an integer to the data stream, and findMedian() returns the median of all elements added so far.
The median is the middle value when the elements are sorted. If the number of elements is even, the median is the average of the two middle values.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
addNum(1)
addNum(2)
findMedian()
addNum(3)
findMedian()
Output
1.5
2.0Solution
This solution uses two heaps to divide the numbers into two halves. A Max Heap stores the smaller half, while a Min Heap stores the larger half.The heaps are balanced so that their sizes differ by at most one. The Max Heap is allowed to contain one extra element when the total number of elements is odd.
When a new number is added, it is first placed in the appropriate heap. The heaps are then rebalanced if necessary.
If both heaps have the same size, the median is the average of their top elements. Otherwise, the top element of the larger Max Heap is the median.
class MedianFinder {
private PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
private PriorityQueue<Integer> minHeap =
new PriorityQueue<>();
public void addNum(int num) {
// Add to the appropriate half.
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
// Rebalance if needed.
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
// Odd number of elements.
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
}
// Even number of elements.
return ((double) maxHeap.peek() + minHeap.peek()) / 2;
}
}
Complexity
Adding a number may require inserting into a heap and rebalancing it, with each heap operation takingO(log n) time.
Finding the median only accesses the top element or elements of the heaps, so it takes
O(1) time. The two heaps together store all added numbers, requiring O(n) space.