02. Find Median from Data Stream

Difficulty:HardPattern:Two Priority Queues / Dynamic MedianTime:Add O(log n), Query O(1)Space:O(n)

Implement a data structure MedianFinder that supports adding numbers from a data stream and finding the median of all elements added so far.

How It Works & Algorithmic Design

Solves using Two Heaps (Max-Heap for Lower Half, Min-Heap for Upper Half):

Data Structure: Maintain maxHeap (stores smaller numbers) and minHeap (stores larger numbers).
addNum(num):
- Push num to maxHeap.
- Balance values: pop root of maxHeap and push to minHeap.
- Balance sizes: if minHeap.size > maxHeap.size, pop root of minHeap and push to maxHeap.
findMedian():
- If maxHeap.size > minHeap.size, median = maxHeap.peek().
- Else, median = (maxHeap.peek() + minHeap.peek()) / 2.

Why This Approach Works Best

Inserts numbers in $O(\log n)$ time and queries median in optimal $O(1)$ constant time.

Example Walkthrough

Stream Operations: addNum(1) -> addNum(2) -> findMedian() -> addNum(3) -> findMedian()

Dynamic insertions.

Median States: After 1,2: median = (1+2)/2 = 1.5. After 1,2,3: median = 2.

Calculates running median.

Output: [1.5, 2.0]

Result sequence.

Answer: Median Finder using Two Priority Queues

class MedianFinder {
  constructor() {
    this.small = []; // Max Heap simulated via sorted array insertion
    this.large = []; // Min Heap simulated
  }
  addNum(num) {
    this.small.push(num);
    this.small.sort((a, b) => b - a);
    this.large.push(this.small.shift());
    this.large.sort((a, b) => a - b);
    if (this.large.length > this.small.length) {
      this.small.push(this.large.shift());
      this.small.sort((a, b) => b - a);
    }
  }
  findMedian() {
    if (this.small.length > this.large.length) return this.small[0];
    return (this.small[0] + this.large[0]) / 2;
  }
}

💡 Balance max-heap and min-heap to access stream median in constant O(1) time.

Key Takeaways

Max-heap stores lower half; Min-heap stores upper half.
Heap size difference is kept at most 1.
addNum takes $O(\log n)$ and findMedian takes $O(1)$ time.