Problem 18.5 · Heaps and Priority QueuesHard

Find Median from Data Stream

PatternTwo Heaps Combine Structures to Design

What it teaches: The two-heaps pattern as a class.

Practise it on judges as “Find Median from Data Stream”.

The problem

Design MedianFinder with addNum(int num) and findMedian() returning the median of all numbers added so far.

Example 1

Input: addNum 1, addNum 2, findMedian, addNum 3, findMedian
Output: 1.5, 2.0

Constraints

Up to 5 × 10⁴ calls
findMedian is called only after at least one addNum

Pattern clues in the wording

→ Running median
→ Middle of a changing collection

These clues point to Two Heaps: Split values into a max-heap of the smaller half and a min-heap of the larger half to read the median instantly.

Stuck? Take one hint at a time

MedianFinder.java · starter

import java.util.*;

class MedianFinder {
    public MedianFinder() {}
    public void addNum(int num) {}
    public double findMedian() { return 0.0; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] args = [[],[1],[2],[],[3],[]]	[null,null,null,1.5,null,2]
2	ops = ["MedianFinder","addNum","addNum","addNum","addNum","findMedian"] args = [[],[5],[15],[1],[3],[]]	[null,null,null,null,null,4]

From slow to fast

Approaches

1. Two heaps · O(log n) add, O(1) median

Two heaps

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

addNum: push into low, move low's top to high, and if high is bigger move its top back. findMedian: low's top, or the average of both tops.

Approach 1

import java.util.*;

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

    public MedianFinder() {}

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

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

Verdict: The standard design.

Before you submit

Edge cases and common mistakes

Test these inputs

One number
Negative numbers
Large values (sum in long)

Mistakes people make

Integer division in the average.
Not rebalancing after each add.

Interview

Follow-up questions

What if all numbers are in 0–100?

Command Palette

The problem

Approaches

Two heaps

Edge cases and common mistakes

Follow-up questions