Free lesson · DSA Mastery - Interview Prep, End to End

Find Median from Data Stream

Medium8 min readdsaheaps

Find Median from Data Stream

Find Median from Data Stream opens the Two Heaps sub-group - the pattern where a max-heap and a min-heap are balanced against each other. To report the running median of a stream, keep the smaller half of the numbers in a max-heap (its top is the largest of the low half) and the larger half in a min-heap (its top is the smallest of the high half); balancing their sizes puts the median at one or both tops. It's the definitive two-heap problem, showing how splitting data into a "low half" and "high half" with opposing heaps turns an O(n)-per-query median into an O(log n) insert with O(1) lookup. We present the sorted-insert baseline and the two-heap design (canonical).

The insight: the median sits at the boundary between the smaller half and the larger half of the data. If you keep the smaller half in a max-heap (largest-of-low on top) and the larger half in a min-heap (smallest-of-high on top), then the two tops straddle the median. Keep the heaps' sizes equal or off by one, and the median is either one top (odd count) or the average of both tops (even count) - all in O(1), with each insertion costing O(log n).

The Problem

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

MedianFinder mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
mf.findMedian(); // 1.5
mf.addNum(3);
mf.findMedian(); // 2.0

Constraints:

• -10^5 <= num <= 10^5
• There will be at least one element before calling findMedian.
• At most 5 * 10^4 calls will be made to addNum and findMedian.

Approaches Overview

The sorted-list approach inserts each number into its position (O(n) shift) so the median is a direct index lookup - fine for few inserts, slow at scale. The two-heap design splits numbers into a low half (max-heap) and high half (min-heap), rebalancing so sizes differ by at most one; the median reads from the tops in O(1) and each insert is O(log n). The two-heap structure is the canonical streaming-median solution.

Approach 1: Sorted List Insert - Baseline

The Idea

Maintain a list kept in sorted order. addNum inserts the value at its correct position (binary search for the spot, then shift - O(n) due to shifting). findMedian reads the middle element (odd) or averages the two middle elements (even) in O(1). Simple, but the per-insert shifting is linear.

Complexity

Time: O(n) per addNum, O(1) per findMedian. Space: O(n).

Approach 2: Two Heaps (Low Max-Heap + High Min-Heap) - Canonical

The Idea

Keep a max-heap low holding the smaller half (so low.peek() is the largest of the low half) and a min-heap high holding the larger half (so high.peek() is the smallest of the high half). Invariant: every element in low ≤ every element in high, and low.size() equals high.size() or is exactly one larger. To addNum: push to low, then move low's top to high (to keep ordering), then if high is larger than low, move high's top back to low (to keep sizes balanced). findMedian: if sizes differ, return low.peek(); else average the two tops.

Logic Flowchart

graph TD
    A["low = max-heap (small half); high = min-heap (large half)"] --> B["addNum(num): low.offer(num)"]
    B --> C["high.offer(low.poll())  // pass largest-of-low up"]
    C --> D{"high.size > low.size?"}
    D -->|Yes| E["low.offer(high.poll())  // rebalance sizes"]
    D -->|No| F["balanced"]
    E --> G["findMedian: sizes equal? avg(low.peek, high.peek) : low.peek"]
    F --> G

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two-heap median. Each number enters the low max-heap, its top passes to the high min-heap to maintain order, and if the high heap grows larger its top returns to low, keeping sizes balanced so the median reads from the tops.

Code

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

    public MedianFinder() {}

    public void addNum(int num) {
        low.offer(num);                 // tentatively to the low half
        high.offer(low.poll());         // move largest-of-low into high (keeps ordering)
        if (high.size() > low.size())   // keep low >= high in size
            low.offer(high.poll());
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();          // odd count: extra in low
        return (low.peek() + (double) high.peek()) / 2.0;          // even: average of tops
    }
}

// Usage:
// addNum(1); addNum(2); findMedian() -> 1.5; addNum(3); findMedian() -> 2.0

This Java code keeps a low max-heap and a high min-heap. Each number is offered to low, low's top moves to high to preserve ordering, and high's top returns to low if high grows larger, so the median is the low top or the average of both tops.

Step-by-Step Walkthrough

A frame-by-frame trace on the example sequence:

graph LR
    F0["add 1: low.offer(1); high.offer(poll 1); high bigger → low.offer(poll 1). low[1], high[]"]
    F1["add 2: low.offer(2)→low[2,1]; high.offer(poll 2)→high[2]. sizes 1,1. median (1+2)/2=1.5"]
    F2["add 3: low.offer(3)→low[3,1]; high.offer(poll 3)→high[2,3]; high>low → low.offer(poll 2)→low[2,1]. high[3]"]
    F3["sizes low 2, high 1 → median low.peek = 2.0"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds running medians. After one and two the heaps hold the low and high halves giving median one point five; after three the low heap has the extra element, giving median two.

Result: 1.5 then 2.0.

Complexity

Time: O(log n) per addNum, O(1) per findMedian. Space: O(n) across both heaps.

Complexity Comparison

The two-heap design makes insertion logarithmic while keeping median lookup constant - the median is always at the heap tops because the heaps partition the data at exactly the middle. This low-half/high-half split with opposing heap orientations is the defining Two Heaps pattern and the standard answer for streaming order statistics.

Variations & Follow-ups

Why does the median always sit at the heap tops?

The two heaps partition all numbers seen so far into a low half and a high half with the invariant that every low-half element is ≤ every high-half element. The max-heap low exposes the largest of the low half at its top; the min-heap high exposes the smallest of the high half at its top. These two values are precisely the elements bordering the middle of the sorted order. If the total count is odd, you let low hold one extra element, so its top is the middle element - the median. If even, the two tops are the two middle elements, and their average is the median. The opposing orientations are what place the relevant boundary elements at O(1)-accessible tops.

Why the offer-to-low, poll-to-high, then maybe-rebalance dance?

Two things must hold after each insert: the ordering invariant (all low ≤ all high) and the size invariant (sizes equal or low one larger). The three-step routine guarantees both regardless of where the new number falls. Offering to low then immediately moving low's top to high ensures the new number ends up on the correct side: if it belonged in the high half, it bubbles to low's top and gets passed up; if it belonged in the low half, some other element gets passed up instead. That step can leave high one too large, so the final check moves high's top back to low when needed. The sequence is a clean, branch-light way to maintain both invariants in O(log n) without case analysis on the new value.

Why keep the extra element in low rather than high?

It's a convention that simplifies findMedian: when the total count is odd, the median is a single element, and by always parking the extra element in low, that element is exactly low.peek() - so the odd case returns low.peek() directly. You could symmetrically favor high instead; you'd just read high.peek() for the odd case. What matters is consistency: pick one side to hold the surplus and size-check accordingly (high.size() > low.size() triggers rebalancing toward low). Mixing conventions, or allowing the sizes to drift by more than one, breaks the O(1) median read.

How does the two-heap pattern generalize beyond the exact median?

The same low-half/high-half split tracks any boundary order statistic of a stream. To find a value at a fixed quantile (say the element such that 70% are below it), keep the heaps' sizes in a 70:30 ratio instead of 50:50; the boundary top gives that percentile. The pattern extends to sliding-window median (next topic) by adding lazy deletion, and to problems like IPO where one heap holds "available" items by one key and another holds "locked" items by another. The core idea - partition data into two opposing heaps balanced by a size rule so a boundary element is always at a top - is the reusable engine; the median is its simplest instance.

What about edge cases?

• First element: Goes to low (after the rebalance), and findMedian returns it.
• Two elements (Example): One in each heap; median is their average.
• Duplicate values: Handled normally; equal elements can sit in either heap, ordering invariant still holds.
• Negative numbers: No special handling; comparisons work as usual.

Common Interview Pitfalls

• Swapping the heap orientations. low must be a max-heap and high a min-heap, or the tops won't border the median.
• Letting sizes drift by more than one. The median read assumes a difference of at most one; rebalance every insert.
• Integer overflow / truncation in the average. Cast to double before averaging the two tops.
• Reading the wrong top for the odd case. Return the top of whichever heap holds the surplus (here, low).

Why This Topic Matters

Find Median from Data Stream is the definitive Two Heaps problem: a low max-heap and a high min-heap partition the data so the median is always at the tops, turning an O(n) sorted-insert into O(log n) insert with O(1) lookup. It establishes the balanced-opposing-heaps technique for streaming order statistics, the foundation for quantile tracking and the sliding-window median that follows.

The next topic, IPO, applies two heaps to a project-selection problem: you can complete at most k projects, each with a capital requirement and a profit, starting with some initial capital, and each completed project's profit adds to your capital for funding later ones. The two-heap technique uses a min-heap of projects ordered by capital (to cheaply find which projects are now affordable) feeding a max-heap of profits among affordable projects (to greedily pick the most profitable one each round). It's a different flavor of two heaps - not balanced halves but a "by one key, then by another" pipeline - broadening the pattern beyond the median.

Back to DSA Mastery - Interview Prep, End to End