Find Median of Data stream

295.Find Median from Data Stream

Heap

Design

Sorting

Problem Statement:

Design a data structure that supports adding numbers and finding their median. The median is the middle value in an ordered integer list. If the size is even, the median is the average of the two middle values.

Example:

Input:

["MedianFinder", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [], [2], []]

→

Output:

[null, null, 1.0, null, 1.5]

Algorithm:

1. Use two heaps: max-heap for left half, min-heap for right half
2. Keep left heap size equal or one more than right heap
3. Balance heaps after each insertion
4. Median is either left top or average of both tops

Complexity:

Time: O(log n) for addNum, O(1) for findMedian | Space: O(n)

Java Solution:

class MedianFinder {
    // Max heap for left half, min heap for right half
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;
    
    public MedianFinder() {
        left = new PriorityQueue<>((a,b) -> -Integer.compare(a,b));  // max heap
        right = new PriorityQueue<>();  // min heap
    }
    
    public void addNum(int num) {
        // Balance heaps after each insert
        left.offer(num);
        right.offer(left.poll());
        if (right.size() > left.size())
            left.offer(right.poll());
    }
    
    public double findMedian() {
        // If even size, average of both tops
        if (left.size() == right.size())
            return (double) (left.peek() + right.peek())/2;
        
        return left.peek();
    }
}

Python Solution:

class MedianFinder:
    def __init__(self):
        # Max heap for left half, min heap for right half
        self.left = []   # Using negative numbers for max heap
        self.right = []
        
    def addNum(self, num: int) -> None:
        # Balance heaps after each insert
        heapq.heappush(self.left, -num)
        heapq.heappush(self.right, -heapq.heappop(self.left))
        
        if len(self.right) > len(self.left):
            heapq.heappush(self.left, -heapq.heappop(self.right))
            
    def findMedian(self) -> float:
        if len(self.left) == len(self.right):
            return (-self.left[0] + self.right[0]) / 2
        return -self.left[0]

C++ Solution:

class MedianFinder {
private:
    priority_queue<int> left;  // max heap
    priority_queue<int, vector<int>, greater<int>> right;  // min heap
    
public:
    MedianFinder() {}
    
    void addNum(int num) {
        // Balance heaps after each insert
        left.push(num);
        right.push(left.top());
        left.pop();
        
        if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }
    
    double findMedian() {
        if (left.size() == right.size())
            return (left.top() + right.top()) / 2.0;
        
        return left.top();
    }
};