70.Find Median from Data Stream

HardBlind 75Heap / Priority Queue · 7/7

Problem

The median is the middle value of a sorted list; for an even count it is the mean of the two middle values. Implement MedianFinder:

MedianFinder() initializes the object.
void addNum(int num) adds an integer from the stream.
double findMedian() returns the median of all numbers added so far (answers within 10^-5 are accepted).

Examples

Input:  ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
        [[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2.0]
Explanation: [1,2] -> (1+2)/2 = 1.5; [1,2,3] -> 2.

Input:  ["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
        [[],[5],[],[-1],[],[10],[]]
Output: [null,null,5.0,null,2.0,null,5.0]
Explanation: [5] -> 5; [-1,5] -> 2; [-1,5,10] -> 5.

Constraints

-10^5 <= num <= 10^5
There is at least one element before findMedian is called.
At most 5 * 10^4 calls in total to addNum and findMedian.

💡 Key Insight

The median only depends on the boundary between the smaller half and the larger half. Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes equal or the lower half one bigger. Then the median is the top of the lower heap (odd count) or the average of both tops (even count): O(log n) to add, O(1) to query.

Brute Force (Sort on Query)

TimeO(1) for addNum; O(n log n) for findMedian.SpaceO(n).

Intuition

Append every number to a list. When asked for the median, sort a copy and read the middle.

Algorithm

addNum: list.add(num).
findMedian: sort the list; if size is odd return list[n/2], else average list[n/2 - 1] and list[n/2].

Visualization

add 5, add -1, add 10 -> list [5,-1,10]
findMedian: sort -> [-1,5,10] -> n = 3 odd -> list[1] = 5

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

    public MedianFinder() {
    }

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

    public double findMedian() {
        Collections.sort(list); // re-sort on every query
        int n = list.size();
        if (n % 2 == 1) {
            return list.get(n / 2);
        }
        return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
    }
}

Complexity

Time: O(1) for addNum; O(n log n) for findMedian.
Space: O(n).

Sorted List with Binary Insertion

TimeO(n) for addNum (O(log n) search + O(n) shift); O(1) for findMedian.SpaceO(n).

Intuition

Keep the list sorted at all times. Binary search finds the insertion point in O(log n); the insertion itself shifts O(n) elements. findMedian becomes O(1) index access.

Algorithm

addNum: binary-search the first index with value >= num, insert there.
findMedian: read the middle element(s) directly.

Visualization

list = [-1, 5], addNum(10)
lo=0, hi=2: mid=1 (5 < 10) -> lo=2 -> insert at 2
list = [-1, 5, 10] -> median list[1] = 5

Code

java

import java.util.ArrayList;
import java.util.List;

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

    public MedianFinder() {
    }

    public void addNum(int num) {
        int lo = 0, hi = list.size();
        while (lo < hi) { // first index with list[idx] >= num
            int mid = (lo + hi) >>> 1;
            if (list.get(mid) < num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        list.add(lo, num); // O(n) shift
    }

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

Complexity

Time: O(n) for addNum (O(log n) search + O(n) shift); O(1) for findMedian.
Space: O(n).

Two HeapsOptimal

TimeO(log n) for addNum (a constant number of heap operations); O(1) for findMedian.SpaceO(n)

Intuition

Split the numbers into two halves:

low: a max-heap with the smaller half — its top is the largest small number.
high: a min-heap with the larger half — its top is the smallest large number.

Invariant: every element of low is <= every element of high, and low.size() is equal to high.size() or one larger. To insert, push into low, move low's top to high (this fixes ordering), and if high became larger, move its top back to low (this fixes sizes).

Algorithm

addNum(num):
- low.offer(num); high.offer(low.poll()).
- If high.size() > low.size(), low.offer(high.poll()).
findMedian():
- If low.size() > high.size(), return low.peek().
- Else return (low.peek() + high.peek()) / 2.0.

Dry Run

Adding 5, -1, 10:

flowchart TD
    A["add 5: low {5} -> move 5 to high<br/>high bigger -> move back<br/>low {5} high {}"] --> M1["median = 5"]
    A --> B["add -1: low {5,-1} -> move 5 to high<br/>low {-1} high {5}"]
    B --> M2["median = (-1 + 5) / 2 = 2.0"]
    B --> C["add 10: low {10,-1} -> move 10 to high<br/>high {5,10} bigger -> move 5 back<br/>low {5,-1} high {10}"]
    C --> M3["median = low top = 5"]

Code

java

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap, smaller half
    private final PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap, larger half

    public MedianFinder() {
    }

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll()); // largest of the small half moves up: keeps low <= high
        if (high.size() > low.size()) {
            low.offer(high.poll()); // rebalance so low has the extra element
        }
    }

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

Complexity

Time: O(log n) for addNum (a constant number of heap operations); O(1) for findMedian.
Space: O(n) — every number lives in one of the heaps.

Complexity Comparison

Approach	addNum	findMedian	Space
Sort on Query	O(1)	O(n log n)	O(n)
Sorted List + Binary Insertion	O(n)	O(1)	O(n)
Two Heaps	O(log n)	O(1)	O(n)

Common Pitfalls

Integer division: (a + b) / 2 truncates — divide by 2.0 to get 1.5.
Only balancing sizes but not ordering: pushing straight into the smaller heap can leave low.peek() > high.peek().
Comparing boxed Integer tops with ==, which compares references for values outside [-128, 127].
Follow-up: if all numbers are in [0, 100], a 101-bucket count array gives O(1) add and O(100) median.