This is a classic LeetCode 295 solution scenario often encountered in technical interviews at top-tier tech companies. The challenge lies not in finding the median once, but in efficiently maintaining the median as data flows in dynamically.

Brute Force Approach for Find Median from Data Stream

A naive approach to solving Find Median from Data Stream involves maintaining a simple list (or dynamic array) of the numbers.

Naive Algorithm

1. Storage: Store incoming numbers in a dynamic array (e.g., ArrayList in Java or vector in C++).
2. Add: Simply append the new number to the list.
3. Find: To find the median, sort the entire list.
   • If the size is odd, return the middle element.
   • If the size is even, return the average of the two middle elements.

Pseudo-code

text
class MedianFinder:
    list = []

    func addNum(num):
        list.append(num)

    func findMedian():
        sort(list)
        n = list.size
        if n is odd:
            return list[n/2]
        else:
            return (list[n/2 - 1] + list[n/2]) / 2.0

Complexity Analysis

• Time Complexity:
  • addNum: $O(1)$ (amortized).
  • findMedian: $O(N \log N)$ due to sorting, where $N$ is the number of elements added so far.
• Space Complexity: $O(N)$ to store the elements.

Why it Fails

While correct, this approach is inefficient for high-frequency queries. The problem constraints allow up to $5 \cdot 10^4$ calls. If we alternate between addNum and findMedian, the total time complexity approaches $O(N^2 \log N)$ or $O(N^2)$ depending on the sorting behavior. This will result in a Time Limit Exceeded (TLE) error. Even keeping the array sorted using insertion sort ($O(N)$ per add) results in an overall $O(N^2)$ complexity, which is too slow.

Core Insight for Find Median from Data Stream

The intuition behind using two heaps stems from the definition of the median. The median effectively partitions a dataset into two halves: a "lower half" containing the smaller elements and an "upper half" containing the larger elements.

To calculate the median, we do not need to know the relative order of elements within the lower half or the upper half. We only need to know:

1. The maximum element of the lower half.
2. The minimum element of the upper half.

If we have these two values, we can compute the median instantly. Heaps are designed precisely for this: a Max-Heap gives us the maximum element in $O(1)$, and a Min-Heap gives us the minimum element in $O(1)$.

The Invariant

The core constraint enforced by the Two Heaps pattern is:

1. Partitioning: All elements in the Max-Heap must be less than or equal to all elements in the Min-Heap.
2. Balancing: The size difference between the two heaps must not exceed 1. This ensures the median is always at the top of one heap or the average of the tops of both heaps.

Visual Description

Imagine the data stream sorted on a horizontal line. We place a cut right in the middle. The left side (smaller numbers) is managed by a Max-Heap, so the "peak" of this heap is the largest value to the left of the cut. The right side (larger numbers) is managed by a Min-Heap, so the "peak" of this heap is the smallest value to the right of the cut. These two peaks are adjacent to the median cut. As new numbers arrive, we adjust the heaps to keep the cut centered.

Execution Flow

Let's trace the algorithm with inputs: [1, 2, 3].

Initialization:

• maxHeap (Lower Half): []
• minHeap (Upper Half): []

1. addNum(1):

• Push 1 to maxHeap. State: maxHeap: [1], minHeap: [].
• Move top of maxHeap to minHeap. State: maxHeap: [], minHeap: [1].
• Balance check: minHeap size (1) > maxHeap size (0). Move top of minHeap to maxHeap.
• Final State: maxHeap: [1], minHeap: [].

2. addNum(2):

• Push 2 to maxHeap. State: maxHeap: [2, 1] (heap ordered), minHeap: [].
• Move top of maxHeap (2) to minHeap. State: maxHeap: [1], minHeap: [2].
• Balance check: Sizes are equal (1 vs 1). No move needed.
• Final State: maxHeap: [1], minHeap: [2].
• findMedian(): Sizes equal. Return (1 + 2) / 2.0 = 1.5.

3. addNum(3):

• Push 3 to maxHeap. State: maxHeap: [3, 1], minHeap: [2].
• Move top of maxHeap (3) to minHeap. State: maxHeap: [1], minHeap: [2, 3].
• Balance check: minHeap size (2) > maxHeap size (1). Move top of minHeap (2) to maxHeap.
• Final State: maxHeap: [2, 1], minHeap: [3].
• findMedian(): maxHeap is larger. Return 2.0.

Proof of Correctness

The correctness relies on the invariant that maxHeap contains the smallest $\lceil N/2 \rceil$ elements and minHeap contains the largest $\lfloor N/2 \rfloor$ elements.

1. Ordering: By pushing to maxHeap and immediately moving the max to minHeap, we ensure that no element in maxHeap is larger than the smallest element in minHeap. The subsequent rebalancing moves the smallest of the large half back to the small half only if necessary to maintain size counts, preserving the relative order property.
2. Size: The logic explicitly enforces that maxHeap.size() is either equal to minHeap.size() (even $N$) or minHeap.size() + 1 (odd $N$).
3. Median Access:
   • If $N$ is odd, the median is the $(N+1)/2$-th element, which is the largest element in the lower half (top of maxHeap).
   • If $N$ is even, the median is the average of the $N/2$-th and $(N/2 + 1)$-th elements. These correspond to the top of maxHeap and top of minHeap respectively.

Reference Implementation

C++ Solution for LeetCode 295

cpp
#include <queue>
#include <vector>

class MedianFinder {
private:
    // Max-heap to store the smaller half of the numbers
    std::priority_queue<int> maxHeap;
    // Min-heap to store the larger half of the numbers
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

public:
    MedianFinder() {
        // Constructor strictly initializes empty heaps
    }
    
    void addNum(int num) {
        // Always add to maxHeap first to let it filter the largest
        maxHeap.push(num);
        
        // Move the largest element of the small half to the large half
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        
        // Rebalance: maxHeap size must be equal to or 1 greater than minHeap size
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            // Odd number of elements: median is the top of maxHeap
            return (double)maxHeap.top();
        } else {
            // Even number of elements: median is average of both tops
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }
};

Java Solution for LeetCode 295

java
import java.util.PriorityQueue;
import java.util.Collections;

class MedianFinder {
    // Max-heap for the lower half
    private PriorityQueue<Integer> maxHeap;
    // Min-heap for the upper half
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        // Max-heap requires reverseOrder comparator
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        
        // Maintain size property: maxHeap can have at most 1 more element than minHeap
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

Python Solution for LeetCode 295

python
import heapq

class MedianFinder:

    def __init__(self):
        # Python's heapq is a min-heap by default.
        # We simulate a max-heap by storing negated numbers.
        self.small = []  # Max-heap (stores -num)
        self.large = []  # Min-heap (stores num)

    def addNum(self, num: int) -> None:
        # Push to max-heap (negate value)
        heapq.heappush(self.small, -num)
        
        # Ensure every element in small is <= every element in large
        # We pop the largest from small (which is -small[0]) and push to large
        val = -heapq.heappop(self.small)
        heapq.heappush(self.large, val)
        
        # Rebalance sizes: small can have 1 more element than large
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

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

Mistake 1: Incorrect Heap Initialization

• What: Using two default min-heaps in languages like C++ or Java without configuring one as a max-heap.
• Why: The pattern requires accessing the maximum of the lower half. A min-heap gives the minimum, which is the wrong end of the lower partition.
• Consequence: The algorithm fails to track the elements closest to the median, returning incorrect values.

Mistake 2: Forgetting to Rebalance

• What: Adding elements to heaps based purely on value comparison without ensuring the sizes remain balanced (diff $\le 1$).
• Why: If one heap grows significantly larger than the other, the "tops" of the heaps no longer represent the median elements.
• Consequence: Correctness failure. The median calculation assumes the heaps meet exactly at the middle index.

Mistake 3: Integer Division in Median Calculation

• What: Returning (a + b) / 2 instead of (a + b) / 2.0 in strictly typed languages.
• Why: If a and b are integers, (a + b) / 2 performs integer division, truncating the decimal.
• Consequence: Precision error. The problem requires a double return type.