Problem #295: Find Median from Data Stream

Intuition & Strategy Breakdown

Use two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half. Keep size balanced within 1 element difference.

Python Solution

import heapq

class MedianFinder:
    def __init__(self):
        # Max-Heap (stores smaller half)
        self.small = [] 
        # Min-Heap (stores larger half)
        self.large = [] 

    def addNum(self, num: int) -> None:
        # Step 1: Push to Max-Heap (negated)
        heapq.heappush(self.small, -num)
        
        # Step 2: Ensure largest of small goes to large
        heapq.heappush(self.large, -heapq.heappop(self.small))
        
        # Step 3: Keep heaps balanced (size diff <= 1)
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0

Java Solution

class MedianFinder {
    private PriorityQueue small = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue large = new PriorityQueue<>();

    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll());
        if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();
        }
        return (small.peek() + large.peek()) / 2.0;
    }
}