Algorithm Day77 - Find Median from Data Stream

Posted on In , , Views:

🧩 Problem Description

The MedianFinder class:

  • MedianFinder() initializes the object.
  • void addNum(int num) adds the integer num to the data structure.
  • double findMedian() returns the median of all elements so far.

💬 Examples

Example 1

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

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

💡 Intuition

To efficiently find the median:

  • Use two heaps:

    • A max-heap (left) to store the smaller half of numbers.
    • A min-heap (right) to store the larger half of numbers.

  • Balancing rule:

    • Either both heaps have equal size, or left has one more element.
    • Median = root of max-heap (if odd) or average of roots (if even).

🔢 Java Code (Two Heaps)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> left;  // max-heap
    private PriorityQueue<Integer> right; // min-heap

    public MedianFinder() {
        left = new PriorityQueue<>(Collections.reverseOrder());
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll());
        
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        } else {
            return (left.peek() + right.peek()) / 2.0;
        }
    }
}

⏱ Complexity Analysis

  • Time (per operation): O(log n)
  • Space: O(n)

✍️ Summary

  • Two Heaps maintain balance between left and right halves.
  • Ensures O(log n) per insertion and O(1) median query.

Related problems

  • lc-480 — Sliding Window Median
  • lc-703 — Kth Largest Element in a Stream
  • lc-220 — Contains Duplicate III