Find Median from Data Stream

Problem in Plain English

Maintain a growing stream of integers and report its median after each batch of insertions. For an odd count the median is the middle value, and for an even count it is the mean of the two middle values.

Problem Statement

Implement MedianFinder(), addNum(num) to retain an arriving integer, and findMedian() to return the median of all retained numbers. Queries do not remove numbers.

In sorted order, an odd count has one middle value; an even count uses the average of the two middle values. A query always follows at least one insertion, and error within $10^{-5}$ is accepted.

Constraints

Each inserted integer lies between $-10^5$ and $10^5$ , inclusive.
Call findMedian only after at least one insertion.
At most $5 \times 10^4$ total calls to addNum and findMedian.

Examples

Example 1

Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2.0]

After 1 and 2 the ordered stream is [1, 2] with median 1.5; after adding 3 the stream is [1, 2, 3] with median 2.0.

Example 2

Input: ["MedianFinder","addNum","findMedian"] [[],[5],[]]
Output: [null,null,5.0]

A single-element stream has itself as the median, so the answer is 5.0.

Example 3

Input: addNum(-5), addNum(-5), findMedian(), addNum(10), findMedian(), addNum(10), findMedian()
Output: [-5.0, -5.0, 2.5]

The successive sorted states are [-5,-5], [-5,-5,10], and [-5,-5,10,10]. Duplicate negatives occupy separate ranks. The even final median averages -5 and 10, giving 2.5.

Intuition

The median depends on rank, not arrival order. After arrivals 1, 2, the two middle ranks contain 1 and 2; adding 3 makes 2 the single middle. Sorting reconstructs those ranks whenever asked. Two heaps instead preserve a boundary between a lower half and an upper half, exposing the middle without ordering every element.

Approaches

Sort on Request

Solution Details

Reveal Sort on Request: intuition, complexity, and code

Intuition

Sorting the stored numbers exposes the middle directly, so the simplest design appends every arrival and sorts only when asked. Each query pays for a full sort, which drags as the stream grows to tens of thousands of values.

Step-by-Step Logic

Initialize an empty collection; every insertion appends one value, giving [1] then [1,2] in Example 1.
On each query, sort all retained values numerically and compute the current size n. The first query has n = 2.
If n is even, average indices n/2-1 and n/2; here they contain 1 and 2, giving 1.5.
Continue appending after a query: adding 3 retains [1,2,3].
For odd n, return index floor(n/2) after sorting; the second query uses index 1 and returns 2.0.

Why It Works

Appending retains every arrival exactly once. Sorting preserves that multiset and places each value at its rank. For odd size n, zero-based index floor(n/2) has equally many values on either side. For even size, indices n/2-1 and n/2 straddle the center, so averaging them is the definition of median. Sorting and querying remove nothing, which makes repeated queries return the same answer until another insertion.

Dry Run

Sort on Request: variable states at each step
call	retained values after call	n	middle index or indices	query result
constructor	`[]`	0	none	null
add 1	`[1]`	1	no query	null
add 2	`[1,2]`	2	no query	null
query: sort	`[1,2]`	2	0 and 1: values 1 and 2	1.5
add 3	`[1,2,3]`	3	no query	null
query: sort	`[1,2,3]`	3	1: value 2	2.0

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

For n retained values, addNum is amortized O(1), with O(n) possible array growth; findMedian is O(n log n) worst case and repeated queries can each pay this cost. Persistent storage is O(n). Java and Python sorting may allocate O(n) temporary references; JavaScript sort scratch storage depends on its engine, ordinarily O(n). No sorted copy is made; total retained plus conventional sort storage is O(n).

Code

Solution.java

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4
5class MedianFinder {6    private List<Integer> values = new ArrayList<>();7
8    public void addNum(int num) {9        values.add(num);10    }11
12    public double findMedian() {13        Collections.sort(values);14        int n = values.size();15        if (n % 2 == 1) {16            return values.get(n / 2);17        }18        // Widen before addition so averaging also works for full-range int values.19        return ((double) values.get(n / 2 - 1) + values.get(n / 2)) / 2.0;20    }21}

Hints

Hint 1

Cut the ordered stream into a lower half and an upper half; the median always sits at the cut.

Hint 2

Keep the lower half in a max-heap and the upper half in a min-heap so both middles are one peek away.

Hint 3

Route each arrival through one heap into the other, then move one value back if the upper half outgrows the lower half.

Edge Cases

A single arrival leaves the upper heap empty: return the lower root without peeking at the upper heap.
Repeated queries must retain all values and return the same median.
Duplicates still occupy distinct ranks; negative values require reversing the sign correctly in Python.
Even counts can produce negative or positive half-integer medians. Java widens before summing, though the stated values themselves fit safely in int.

Common Mistakes and Interview Tips

Balancing sizes alone without the ordering invariant: equal heaps can still expose the wrong ranks.
Returning the upper root for an odd count when this implementation assigns the extra entry to the lower half.
Using integer division for an even count, or converting only after an overflowing integer addition.
Forgetting that Python stores negated lower values, or using JavaScript default lexicographic sorting.
Removing roots to answer a query; use peeks so later queries see the entire stream.

Key Takeaway

To track the middle of a growing set, hold the lower half in a max-heap and the upper half in a min-heap so the boundary, and therefore the median, is always on top.