Find Median from Data Stream

Hard Problem 84 of 151 Java and Python

Problem

Design a MedianFinder with addNum(num), which adds an integer from a data stream, and findMedian(), which returns the median of all numbers so far.

The median is the middle value of the sorted list, or the average of the two middle values when the count is even.

Example 1

Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, then 2.0

Constraints

-10⁵ ≤ num ≤ 10⁵
Up to 5 × 10⁴ calls; findMedian is only called after at least one add.

Explanation

Split the numbers into a lower half and an upper half. The median only depends on the largest of the lower half and the smallest of the upper half.

Keep the lower half in a max-heap and the upper half in a min-heap, with the lower heap allowed one extra element. Each insert costs O(log n) and the median is read from the tops.

Approach 1 · Naive

Sorted list with insertion

Time O(n) add, O(1) median
Space O(n)

Keep the numbers in a sorted list, inserting each new number at its place with binary search.

addNum: find the insert position by binary search and insert (shifting elements).
findMedian: read the middle element(s).

Java

import java.util.*;

class MedianFinder {
    private final List<Integer> sorted = new ArrayList<>();

    public void addNum(int num) {
        int i = Collections.binarySearch(sorted, num);
        sorted.add(i < 0 ? -i - 1 : i, num);
    }

    public double findMedian() {
        int n = sorted.size();
        return n % 2 == 1 ? sorted.get(n / 2) : (sorted.get(n / 2 - 1) + sorted.get(n / 2)) / 2.0;
    }
}

Python

import bisect

class MedianFinder:
    def __init__(self):
        self.sorted = []

    def addNum(self, num: int) -> None:
        bisect.insort(self.sorted, num)

    def findMedian(self) -> float:
        n = len(self.sorted)
        if n % 2:
            return float(self.sorted[n // 2])
        return (self.sorted[n // 2 - 1] + self.sorted[n // 2]) / 2

Approach 2 · Optimal

Two heaps

Time O(log n) add, O(1) median
Space O(n)

A max-heap low holds the smaller half and a min-heap high holds the larger half; low may hold one extra.

addNum: push into low, then move low's top into high (keeps every low ≤ every high).
If high is now bigger than low, move high's top back into low.
findMedian: if low is bigger, its top; otherwise the average of both tops.

Java

import java.util.*;

class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> high = new PriorityQueue<>();

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) {
            low.offer(high.poll());
        }
    }

    public double findMedian() {
        if (low.size() > high.size()) {
            return low.peek();
        }
        return (low.peek() + high.peek()) / 2.0;
    }
}

Python

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap via negatives
        self.high = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Complexity compared

Approach	Time	Space
Naive Sorted list with insertion	O(n) add, O(1) median	O(n)
Optimal Two heaps	O(log n) add, O(1) median	O(n)

Key takeaways

Routing every number through low and then high keeps the halves ordered without extra comparisons.
Sliding Window Median is the harder sibling: the same two heaps plus lazy deletion.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem