← Back to Heap Pattern

📚 Find Median from Data Stream – Java Cheat Sheet

📌 What Is It?

The problem involves finding the median of a stream of integers in real-time. The median is the middle value in a sorted list of numbers, or the average of the two middle values if the list has an even number of elements.

To solve this efficiently, we use two heaps:

• Max-Heap: Stores the smaller half of the numbers (largest number at the top).
• Min-Heap: Stores the larger half of the numbers (smallest number at the top).

The heaps are balanced such that the size difference between them is at most 1. This allows us to calculate the median in constant time by looking at the top elements of the heaps.

🧱 Pattern Template

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // Stores the smaller half
    private PriorityQueue<Integer> minHeap; // Stores the larger half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // Add to maxHeap first
        maxHeap.offer(num);

        // Balance heaps: Ensure all elements in maxHeap are <= elements in minHeap
        minHeap.offer(maxHeap.poll());

        // Maintain size property: maxHeap can have at most one more element than minHeap
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

📊 Time Complexity

• addNum(): O(log n) – Adding a number to a heap and balancing the heaps both take logarithmic time.
• findMedian(): O(1) – Retrieving the median is a constant-time operation as it only involves peeking at the top elements of the heaps.
• Overall Complexity: Efficient for real-time median calculation in dynamic data streams.

✅ Use Cases

• Real-time median calculation
• Dynamic data streams
• Efficiently handling large datasets

📘 Common LeetCode Problems

• 295. Find Median from Data Stream [Hard] Two Heaps

🧪 Example: Find Median from Data Stream

Input:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

Output:
[null, null, null, 1.5, null, 2.0]

Explanation:
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (median of [1, 2])
medianFinder.addNum(3);    // arr = [1, 2, 3]
medianFinder.findMedian(); // return 2.0 (median of [1, 2, 3])

▶️ View Animation

💡 Pro Tips

• Use a max-heap for the smaller half and a min-heap for the larger half
• Always balance the heaps to maintain the size property
• Edge cases: empty stream, single element, large datasets