A latency overlay wants the live p50 of request times as they arrive — operators watch that median to decide if the cluster is drifting. The first version stored every sample and sorted on each arrival. A dozen ticks painted instantly. A blotter with tens of thousands of arrivals was still sorting the whole log when the panel lagged a cycle.

Find Median from Data Stream asks for the median after every add. Two heaps already give the middle: a max-heap of the lower half and a min-heap of the upper half. Sorting the whole history uses that answer and still pays a full sort per tick.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Invert the lower half so peek is the largest of the small numbers. Kth Largest in a Stream keeps one size-k min-heap because k is known. Here the middle seat moves as n grows, so you need two heaps.

The problem

Design a class. addNum(int num) inserts into the stream. findMedian() returns the median of every number seen so far as a double. If the count is odd, the middle value. If even, the average of the two middle values.

addNum(12)
findMedian()  →  12.0     // stream 12

addNum(4)
findMedian()  →  8.0      // 4, 12

addNum(19)
findMedian()  →  12.0     // 4, 12, 19

addNum(7)
findMedian()  →  9.5      // 4, 7, 12, 19

Note: The prompt usually promises at least one addNum before findMedian. At the board, ask; do not peek an empty heap.

Store every number and sort on add is the honest brute force

Keep a list. addNum appends and sorts. findMedian reads the middle index, or averages the two middle seats when the count is even. Correct. Slow in the stream length.

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

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

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

At a dozen samples this is a rounding error. At tens of thousands of adds you paid a full sort for a question two heaps answer with a few offers and polls: what sits at the seam of the lower half and the upper half?

Inserting at the sorted index (Collections.binarySearch, then list.add(i, num)) still shifts O(n) elements. Same bill, nicer constant.

Two heaps: max-heap below, min-heap above

lower is a max-heap — PriorityQueue with Collections.reverseOrder(). Peek is the largest of the small numbers. Say the invert out loud. upper is a natural-order min-heap. Peek is the smallest of the large numbers.

Invariant: every value in lower is ≤ every value in upper, and the sizes differ by at most one. Typical add keeps lower equal or one larger:

  • Offer the new value into lower.
  • Poll lower’s max into upper. That move keeps the order: the largest of the small half is now a candidate for the large half.
  • If upper is now bigger, poll its min back into lower.

Then the median is lower.peek() when the count is odd, or (lower.peek() + upper.peek()) / 2.0 when even. Use / 2.0, not integer division.

You never sort the history. You never keep a single heap hoping the root is the middle.

addNum(12)  offer 12 → lower
            poll 12 → upper
            upper bigger → poll 12 → lower
            lower [12]  upper []              median 12.0

addNum(4)   offer 4 → lower                   lower [12, 4]
            poll 12 → upper                   lower [4]  upper [12]
            sizes equal
            median (4 + 12) / 2.0 = 8.0

addNum(19)  offer 19 → lower                  lower [19, 4]
            poll 19 → upper                   lower [4]  upper [12, 19]
            upper bigger → poll 12 → lower    lower [12, 4]  upper [19]
            median 12.0

addNum(7)   offer 7 → lower                   lower [12, 4, 7]
            poll 12 → upper                   lower [7, 4]  upper [12, 19]
            sizes equal
            median (7 + 12) / 2.0 = 9.5

The Java is that walk. findMedian never sorts. Both peeks sit at the roots after the rebalance.

class MedianFinder {
    final PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
    final PriorityQueue<Integer> upper = new PriorityQueue<>();

    void addNum(int num) {
        lower.offer(num);
        upper.offer(lower.poll());
        if (upper.size() > lower.size()) {
            lower.offer(upper.poll());
        }
    }

    double findMedian() {
        if (lower.size() > upper.size()) {
            return lower.peek();
        }
        return (lower.peek() + (double) upper.peek()) / 2.0;
    }
}

Each add is O(log n) — a constant number of offers and polls. findMedian is O(1) — one or two peeks. Space is O(n) — every number stays in one of the two heaps. Do not re-lecture sift at the whiteboard unless they ask.

Note: (a + b) / 2 is integer division. The return type is double. Use / 2.0. A natural-order lower would peek the smallest of the small half, which is not the seam.

What interviewers usually poke next

  • Even vs odd count. Odd: lower is one larger, median is lower.peek(). Even: sizes match, average the two peeks. The rebalance above is what keeps that split; do not re-count n on every findMedian unless you want a second source of truth to drift.
  • All duplicates. They occupy distinct seats. A stream of nines still splits across both heaps; both peeks are 9, and the even average is still 9.0. This is not a unique-key ranking.
  • Why one heap is not enough. Kth Largest in a Stream needs k up front, so a size-k min-heap’s peek is the answer. Median’s “k” is n/2, and n grows. You cannot size one heap to a moving middle. Kth Largest in an Array is the frozen cousin: one-shot kth, no surviving class, still not a live median.
  • Sorted list / TreeMap. Binary-insert into an ArrayList is O(n) shifts. A TreeMap of counts is O(log n) per add, but walking to the middle is still linear unless you maintain extra pointers. Two heaps keep both peeks at the roots.
  • Overflow. lower.peek() + upper.peek() unboxes to int before / 2.0. Widen first: (lower.peek() + (double) upper.peek()) / 2.0. Tiny interview ranges hide it; production blotters do not.

You are done with this problem when you can say, out loud, why sorting on every add is correct, why two heaps of opposite polarity peek the seam, and why a size-k min-heap is the wrong bill when k is the moving middle.