Find Median from Data Stream

leetcode.com

Problem Statement

Design a data structure that supports:

addNum(int num)
findMedian()

Return the median after every insertion.

---

Brute Force Intuition

Store all numbers in a list.

Whenever median is requested:

Collections.sort(nums);

Then compute median.

Complexity

Operation	Complexity
addNum	O(1)
findMedian	O(N log N)

Brute Force Code

class MedianFinder {

    List<Integer> nums;

    public MedianFinder() {
        nums = new ArrayList<>();
    }

    public void addNum(int num) {
        nums.add(num);
    }

    public double findMedian() {

        Collections.sort(nums);

        int n = nums.size();

        if (n % 2 == 1)
            return nums.get(n / 2);

        return (nums.get(n / 2)
              + nums.get(n / 2 - 1))
              / 2.0;
    }
}

---

Moving Towards the Optimal Approach

We only need:

Left Half
Right Half

Median depends only on middle elements.

Maintain:

Max Heap → Left Half

Min Heap → Right Half

---

Key Observation

MaxHeap Top
=
Largest element in left half

MinHeap Top
=
Smallest element in right half

Median can be computed instantly.

---

Optimal Java Solution

class MedianFinder {

    PriorityQueue<Integer> left =
        new PriorityQueue<>(Collections.reverseOrder());

    PriorityQueue<Integer> right =
        new PriorityQueue<>();

    public void addNum(int num) {

        left.add(num);

        right.add(left.poll());

        if (right.size() > left.size()) {
            left.add(right.poll());
        }
    }

    public double findMedian() {

        if (left.size() > right.size())
            return left.peek();

        return (left.peek()
              + right.peek()) / 2.0;
    }
}

---

Complexity Analysis

Operation	Complexity
addNum	O(log N)
findMedian	O(1)

---

Interview One-Liner

Maintain two heaps representing left and right halves of the stream and compute the median from heap tops.