Find Median from Data Stream

1. Problem & Core Objective

Support two operations on a stream of integers:

void   addNum(int num)
double findMedian()      // median of everything added so far

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

addNum(1); addNum(2);
findMedian()   → 1.5
addNum(3);
findMedian()   → 2.0

Constraints: -10^5 <= num <= 10^5 · up to 5 × 10^4 calls · findMedian is only called after at least one addNum

What's actually being tested: the two-heap structure. It's the canonical answer, and the interesting part is why two heaps rather than one — a single heap exposes an extreme, and the median is precisely the element furthest from both extremes.

2. First-Principles Thought Process

Why one heap can't do it

A heap gives O(1) access to the minimum or the maximum. The median is neither — it's the middle. In a heap of n elements, the median sits somewhere among the leaves with no way to locate it faster than O(n).

So a single heap is the wrong shape, and that's worth saying explicitly rather than just reaching for two.

The reframe

Split the data into two halves at the median:

• the smaller half — you need its largest element
• the larger half — you need its smallest element

Each of those is an extreme, and each is exactly what a heap provides.

• a max-heap holds the smaller half → its root is the largest small value
• a min-heap holds the larger half → its root is the smallest large value

The median is one root (odd total) or the mean of both (even total), readable in O(1).

The two invariants

1. Ordering — every value in the max-heap is ≤ every value in the min-heap.
2. Balance — their sizes differ by at most 1.

Invariant 1 makes the roots be the middle elements. Invariant 2 keeps the split at the median rather than somewhere else.

The add step that preserves both

The naive "put it in whichever heap it belongs to" breaks invariant 1, because you'd have to compare against a root and handle edge cases. The clean trick is to route every value through both heaps:

maxHeap.offer(num);                  // always enter on the low side
minHeap.offer(maxHeap.poll());       // push its largest across
if (minHeap.size() > maxHeap.size())
    maxHeap.offer(minHeap.poll());   // rebalance

Step 2 guarantees ordering: whatever ends up in the min-heap arrived via the max-heap's root, so it was at least as large as everything remaining there. Step 3 restores balance.

This is worth understanding rather than memorising — the reason it's unconditional is that the routing itself enforces the ordering, so there are no comparisons and no special cases.

Which heap gets the extra element

I let the max-heap hold the extra when the count is odd. So:

findMedian() = maxHeap.size() > minHeap.size()
             ? maxHeap.peek()
             : (maxHeap.peek() + minHeap.peek()) / 2.0;

The / 2.0 matters — integer division would truncate 1.5 to 1.

3. Solution Paths

Approach 1 — Keep a list and sort on each query (brute force)

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

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

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

• Time addNum O(1), findMedian O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "What's the total cost across all calls?"

With 5 × 10^4 calls split between adds and queries, each sort is up to 5 × 10^4 × 16 ≈ 8 × 10^5, so roughly 2 × 10^10 overall. Far too slow.

And it re-sorts data that was already sorted on the previous call, differing by one element. That's the signal to maintain order incrementally rather than rebuild it.

⭐ "Insert into a sorted list instead — does that fix it?"

It's the natural next step: binary search for the position in O(log n), then findMedian is O(1) indexing. But the insert itself shifts elements, O(n) on an ArrayList, so it's O(n) per add — about 1.25 × 10^9 total. Still too slow, though much closer.

The heaps get O(log n) per add because they don't maintain a full ordering, only enough to expose the two middle elements.

"Would a TreeMap multiset work?"

Insert is O(log n), but finding the median means walking to the middle, which is O(n) without augmentation. With subtree sizes stored in each node it becomes O(log n) — an order-statistic tree — and that genuinely works. Java has no built-in one, so you'd implement it. The two heaps are far less code for the same bound.

Approach 2 — Two heaps (optimal)

class MedianFinder {
    private final PriorityQueue<Integer> maxHeap =      // smaller half
        new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> minHeap =      // larger half
        new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);                     // 1. always enter on the low side
        minHeap.offer(maxHeap.poll());          // 2. push its largest across — enforces ordering
        if (minHeap.size() > maxHeap.size())    // 3. rebalance; max-heap keeps any extra
            maxHeap.offer(minHeap.poll());
    }

    public double findMedian() {
        return maxHeap.size() > minHeap.size()
             ? maxHeap.peek()
             : (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

Trace — adding 1, 2, 3:

• Time addNum O(log n), findMedian O(1) · Space O(n)

Counter-questions on this approach

⭐ "Why two heaps instead of one?"

Because a heap exposes an extreme, and the median is the element furthest from both extremes. In a single heap the median sits among the leaves with no structure to find it — O(n).

Splitting at the median converts one hard question into two easy ones: the largest of the small half, and the smallest of the large half. Both are extremes, so each is a heap's natural output.

⭐ "Explain the three lines of addNum. Why route through both heaps unconditionally?"

Because the routing is what enforces the ordering invariant, so no comparison is needed.

Line 1 puts the value in the max-heap regardless of size. Line 2 moves the max-heap's largest to the min-heap — and since that was the largest of the low side, everything remaining in the max-heap is ≤ it, and it's now the smallest thing entering the high side. So invariant 1 holds automatically.

Line 3 only fixes sizes.

The alternative — "compare against a root and insert into the right heap" — also works but needs an empty-heap check and gets the comparison boundary wrong easily. The unconditional version has no branches on data.

⭐ "What if you rebalanced before transferring?"

Then the ordering invariant could break. Suppose the max-heap is the smaller one and a large value arrives — rebalancing first would move it straight into the max-heap while a smaller value sits in the min-heap, violating "every max-heap value ≤ every min-heap value".

The order offer → transfer → rebalance is forced, and it's the part worth stating deliberately rather than reciting.

⭐ "Why / 2.0 and not / 2?"

Integer division truncates. (1 + 2) / 2 is 1, not 1.5. The 2.0 promotes the sum to double before dividing.

The sum itself is safe: values are bounded by 10^5, so two of them reach 2 × 10^5, far inside int. With unbounded values I'd write maxHeap.peek() / 2.0 + minHeap.peek() / 2.0 to avoid the intermediate overflow — worth mentioning as the general form.

"Could you let the min-heap hold the extra instead?"

Yes, symmetrically — you'd rebalance the other way and read minHeap.peek() for the odd case. Either convention works as long as findMedian matches it. Mixing them is a silent off-by-one that returns the wrong side of the median.

"What's the size relationship exactly?"

Either equal, or the max-heap has exactly one more. It can never be two more, because line 3 fixes any imbalance immediately, and each addNum changes the total by one.

"Does it handle duplicates?"

Yes. Both heaps allow duplicates, and the median of [2,2,2] is 2, which falls out correctly. A structure that deduplicated — a TreeSet — would be wrong here for the same reason as in question 1.

Approach 3 — Order-statistic tree / indexed structure

A balanced BST with subtree sizes stored in each node supports "find the element at rank r" in O(log n), so the median is a rank query.

• Time O(log n) both · Space O(n)

Counter-questions on this approach

⭐ "Same complexity. Why isn't this the answer?"

Java has no built-in order-statistic tree, so you'd implement a balanced BST with size augmentation — a few hundred lines, versus about ten for two heaps. Same asymptotics, far more that can go wrong.

It does support more: arbitrary rank queries, range counts, and deletion of a specific value. If the interface needed any of those, it would win. For a median it's over-built.

"When would you actually reach for it?"

If the follow-up added "remove a value from the stream" or "give me the p95, not just the median". Both are awkward with two heaps and natural with rank queries.

Comparison

4. Why the Optimal Wins

Sorting per query recomputes an ordering that changed by one element. A sorted list fixes the query but pays O(n) shifting per insert. Both maintain more order than the question needs — a full ordering, when only the two middle elements are ever read.

The two heaps maintain exactly the necessary structure: a partition at the median, with each side ordered just enough to expose the element adjacent to the split. Everything else stays unordered, which is why inserts are O(log n).

The framing worth keeping:

A heap gives you an extreme; the median is not an extreme. Split the data at the median and the two elements you need become extremes of their own halves — one max-heap, one min-heap, facing each other.

The routing trick is the second half: offer to one side, push its root across, then rebalance — no comparisons, so no boundary cases.

5. Java Prerequisites

Two heaps facing each other

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // small half
PriorityQueue<Integer> minHeap = new PriorityQueue<>();                          // large half

The unconditional add — order is load-bearing:

maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());

Floating-point division

(a + b) / 2      // int division — truncates
(a + b) / 2.0    // promotes to double
a / 2.0 + b / 2.0   // the overflow-safe form for large values

Overflow check. |num| <= 10^5, so a + b <= 2 × 10^5 — int is safe here.

Boxing. PriorityQueue<Integer> boxes; at 5 × 10^4 values that's 50,000 objects. Acceptable, but an int[]-backed heap would avoid it if the scale grew.

6. Interview Communication Guide

Clarifying questions: Can values repeat (yes — rules out a TreeSet)? Is findMedian called more often than addNum (it favours O(1) queries)? Are values bounded (10^5 — it affects the bucket-counting follow-up)? Can values be removed (no, but it's the natural follow-up)?

The pitch

"The difficulty is that a heap gives O(1) access to an extreme, and the median is precisely the element furthest from both extremes. In a single heap it would be somewhere among the leaves — O(n) to find. So one heap is the wrong shape.

The reframe: split the data into a smaller half and a larger half at the median. Then the two elements I need are the largest of the small half and the smallest of the large half — and both of those are extremes.

So: a max-heap for the smaller half, a min-heap for the larger. The median is one root if the count is odd, or the mean of both roots if even. O(1) to read.

Two invariants to maintain: every value in the max-heap is ≤ every value in the min-heap, and their sizes differ by at most one.

The add is three unconditional lines. Offer the value to the max-heap; move the max-heap's root to the min-heap; then if the min-heap is now bigger, move its root back.

The reason to do it that way rather than comparing against a root is that the routing itself enforces the ordering. Whatever lands in the min-heap arrived as the max-heap's largest, so it's ≥ everything left there. No comparisons, so no boundary cases and no empty-heap checks.

The order matters: offer, transfer, rebalance. Rebalancing first could push a large value into the max-heap while a smaller one sits in the min-heap, breaking the ordering.

O(log n) per add, O(1) per query.

One detail — dividing by 2.0, not 2, or (1 + 2) / 2 truncates to 1 instead of 1.5."

Edge cases to volunteer:

Name the two monotonic-input cases. Ascending and descending inputs exercise the rebalance in opposite directions, and an implementation that only ever moves one way passes one and fails the other.

7. Follow-Up Questions — Modified Constraints

⭐ "All numbers are in the range [0, 100]."

Then counting beats heaps: a 101-element frequency array, and the median is found by scanning the counts accumulating until you pass n/2. addNum becomes O(1) and findMedian O(100) — a constant. With a prefix-sum structure or a Fenwick tree over the buckets you can get the query to O(log 100) too.

This is the standard follow-up and it's worth reaching for: a bounded value range usually beats a comparison-based structure.

⭐ "99% of the numbers are in [0, 100], but the rest can be anything."

Hybrid: a bucket array for the common range plus two small heaps for the outliers, tracking how many fall below and above the bucketed range. The median is then located by counting — the buckets answer most queries in O(1) and the heaps handle the tail.

"Support removing a number from the stream."

Hard with heaps — PriorityQueue.remove(Object) is O(n). The standard fix is lazy deletion: keep a map of pending removals and discard stale entries when they surface at a root, adjusting the size counters accordingly. Alternatively switch to an order-statistic tree, where deletion is O(log n) natively. This is the case where the heaps' simplicity stops paying.

"Give me the p95 instead of the median."

The two-heap split is specific to the 50th percentile — you'd rebalance to a 95/5 size ratio instead, which works but is fiddly. For arbitrary percentiles an order-statistic tree is the right structure, or a streaming sketch like t-digest if approximation is acceptable.

"The stream is too large to store."

Exact medians need O(n) space in the worst case — you cannot do better without approximating. Use a quantile sketch: t-digest or Greenwald-Khanna, both of which give bounded-error quantiles in O(log n) or better memory. Worth naming the impossibility before offering the approximation.

"Median of a sliding window rather than the whole stream."

LeetCode 480. The two heaps still work, but you must remove the element leaving the window — which brings back the O(n) removal problem. Lazy deletion with a count map is the usual answer, or a TreeMap multiset with careful size bookkeeping. Notably harder than the unbounded-stream version.