Problem
Design a class that supports adding integers from a stream and finding the median in O(log n) per add and O(1) for median.
Example
Input: add(1), add(2), findMedian()
Output: 1.5Solution
Two heaps: max-heap for lower half, min-heap for upper half. Keep them balanced.
import heapq
class MedianFinder:
def __init__(self):
self.lower = [] # max-heap (negated)
self.upper = [] # min-heap
def add_num(self, num):
heapq.heappush(self.lower, -num)
heapq.heappush(self.upper, -heapq.heappop(self.lower))
if len(self.upper) > len(self.lower):
heapq.heappush(self.lower, -heapq.heappop(self.upper))
def find_median(self):
if len(self.lower) > len(self.upper):
return -self.lower[0]
return (-self.lower[0] + self.upper[0]) / 2class MedianFinder {
constructor() { this.nums = []; }
addNum(num) {
let l = 0, r = this.nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (this.nums[mid] < num) l = mid + 1;
else r = mid;
}
this.nums.splice(l, 0, num);
}
findMedian() {
const n = this.nums.length;
if (n % 2) return this.nums[Math.floor(n / 2)];
return (this.nums[n / 2 - 1] + this.nums[n / 2]) / 2;
}
}class MedianFinder {
priority_queue<int> lower; // max-heap
priority_queue<int, vector<int>, greater<int>> upper; // min-heap
public:
void addNum(int num) {
lower.push(num);
upper.push(lower.top()); lower.pop();
if (upper.size() > lower.size()) {
lower.push(upper.top()); upper.pop();
}
}
double findMedian() {
if (lower.size() > upper.size()) return lower.top();
return (lower.top() + upper.top()) / 2.0;
}
};class MedianFinder {
PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> upper = new PriorityQueue<>();
public void addNum(int num) {
lower.offer(num);
upper.offer(lower.poll());
if (upper.size() > lower.size()) lower.offer(upper.poll());
}
public double findMedian() {
if (lower.size() > upper.size()) return lower.peek();
return (lower.peek() + upper.peek()) / 2.0;
}
}Complexity
- Time: O(log n) add, O(1) median
- Space: O(n)
Explanation
Lower heap stores the smaller half (max at top). Upper heap stores the larger half (min at top). Median is at the top(s).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?