Find Median from Data Stream

LeetCode 295: Find Median from Data Stream Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses two priority queues (heaps) to maintain the lower and upper halves of the data stream, allowing access to the median in $O(1)$ time and insertion in $O(\log N)$ time.

The Find Median from Data Stream problem asks us to design a data structure that supports two operations: adding an integer to a running stream of numbers and retrieving the median of all numbers added so far. The median is defined as the middle value in an ordered list. If the list has an even number of elements, the median is the average of the two middle values.

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

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.

Algorithm Strategy: Heap (Priority Queue) Patterns

We maintain two heaps:

1. maxHeap: Stores the smaller half of the numbers.
2. minHeap: Stores the larger half of the numbers.

Maintaining the Property

When a new number arrives, we cannot simply decide which heap to put it in based on size alone, because we must maintain the size balance.

The strategy involves a "give and take" approach:

1. Add to Max-Heap first: To ensure the new number is compared against the lower half, we push it to maxHeap.
2. Move largest of lower half to upper half: Since we just added to maxHeap, we might have violated the order property (the new number might belong in the upper half). We pop the top of maxHeap (the largest of the smalls) and push it to minHeap.
3. Rebalance sizes: Now minHeap might have too many elements. If minHeap has more elements than maxHeap, we pop the top of minHeap and move it back to maxHeap.

This specific sequence guarantees that:

• maxHeap stores the smaller half.
• minHeap stores the larger half.
• maxHeap.size() is either equal to minHeap.size() or exactly 1 greater.

Finding the Median

• If maxHeap has more elements, the median is maxHeap.top().
• If sizes are equal, the median is (maxHeap.top() + minHeap.top()) / 2.0.

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.

Pattern Reuse Notes

The Two Heaps pattern is a specialized technique primarily used for dynamic median or percentile tracking.

• LeetCode 1825: Finding MK Average: This problem extends the concept. Instead of just two heaps, it conceptually divides the stream into three parts (smallest $K$, middle, largest $K$) to calculate a trimmed average. While often solved with multiset or Fenwick trees, the intuition of maintaining partitions of sorted data remains similar.

Reference Implementation

C++ Solution for LeetCode 295

1#include <queue>
2#include <vector>
3
4class MedianFinder {
5private:
6    // Max-heap to store the smaller half of the numbers
7    std::priority_queue<int> maxHeap;
8    // Min-heap to store the larger half of the numbers
9    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
10
11public:
12    MedianFinder() {
13        // Constructor strictly initializes empty heaps
14    }
15    
16    void addNum(int num) {
17        // Always add to maxHeap first to let it filter the largest
18        maxHeap.push(num);
19        
20        // Move the largest element of the small half to the large half
21        minHeap.push(maxHeap.top());
22        maxHeap.pop();
23        
24        // Rebalance: maxHeap size must be equal to or 1 greater than minHeap size
25        if (minHeap.size() > maxHeap.size()) {
26            maxHeap.push(minHeap.top());
27            minHeap.pop();
28        }
29    }
30    
31    double findMedian() {
32        if (maxHeap.size() > minHeap.size()) {
33            // Odd number of elements: median is the top of maxHeap
34            return (double)maxHeap.top();
35        } else {
36            // Even number of elements: median is average of both tops
37            return (maxHeap.top() + minHeap.top()) / 2.0;
38        }
39    }
40};

Java Solution for LeetCode 295

1import java.util.PriorityQueue;
2import java.util.Collections;
3
4class MedianFinder {
5    // Max-heap for the lower half
6    private PriorityQueue<Integer> maxHeap;
7    // Min-heap for the upper half
8    private PriorityQueue<Integer> minHeap;
9
10    public MedianFinder() {
11        // Max-heap requires reverseOrder comparator
12        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
13        minHeap = new PriorityQueue<>();
14    }
15    
16    public void addNum(int num) {
17        maxHeap.offer(num);
18        minHeap.offer(maxHeap.poll());
19        
20        // Maintain size property: maxHeap can have at most 1 more element than minHeap
21        if (minHeap.size() > maxHeap.size()) {
22            maxHeap.offer(minHeap.poll());
23        }
24    }
25    
26    public double findMedian() {
27        if (maxHeap.size() > minHeap.size()) {
28            return maxHeap.peek();
29        } else {
30            return (maxHeap.peek() + minHeap.peek()) / 2.0;
31        }
32    }
33}

Python Solution for LeetCode 295

1import heapq
2
3class MedianFinder:
4
5    def __init__(self):
6        # Python's heapq is a min-heap by default.
7        # We simulate a max-heap by storing negated numbers.
8        self.small = []  # Max-heap (stores -num)
9        self.large = []  # Min-heap (stores num)
10
11    def addNum(self, num: int) -> None:
12        # Push to max-heap (negate value)
13        heapq.heappush(self.small, -num)
14        
15        # Ensure every element in small is <= every element in large
16        # We pop the largest from small (which is -small[0]) and push to large
17        val = -heapq.heappop(self.small)
18        heapq.heappush(self.large, val)
19        
20        # Rebalance sizes: small can have 1 more element than large
21        if len(self.large) > len(self.small):
22            val = heapq.heappop(self.large)
23            heapq.heappush(self.small, -val)
24
25    def findMedian(self) -> float:
26        if len(self.small) > len(self.large):
27            return -self.small[0]
28        else:
29            return (-self.small[0] + self.large[0]) / 2.0