Find Median from Data Stream

HardTwo Heaps · Design🧩 Two Heaps LeetCode #295 ↗Updated Oct 30, 2026

Problem

Build a class MedianFinder that receives integers one by one through addNum(num) and, at any moment, returns the median of everything seen so far via findMedian(). For an even count the median is the average of the two middle values.

Inputadd(1) add(2) findMedian()Output1.5

Inputadd(3) findMedian()Output2.0

-10⁵ ≤ num ≤ 10⁵ · findMedian only after ≥ 1 add · ≤ 5·10⁴ calls · Follow-up: all nums in [0,100]? 99% of them?

Try it yourself

Java

class MedianFinder {
    public void addNum(int num) {
        
    }

    public double findMedian() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The median only depends on the boundary between the smaller half and the larger half. Keep the smaller half in a max-heap and the larger half in a min-heap; their tops are exactly the middle element(s).

PatternTwo Heaps

Instinct When you need the middle of a changing collection, or best-of-one-pile fed by another pile, split it into a max-heap low half and a min-heap high half.

Memory hack Small fries in a max-heap, big fish in a min-heap; the median lives on the shoreline between them.

Open the Two Heaps guide →

Approaches

Brute ForceStore All, Sort on Query

Time O(1) add, O(n log n) findSpace O(n)

Append each number to a list. When asked for the median, copy and sort the list and read the middle one or two values. Nothing clever is maintained between calls, so every query pays a full sort.

Java

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

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

    public double findMedian() {
        List<Integer> s = new ArrayList<>(nums);
        Collections.sort(s);
        int n = s.size();
        if (n % 2 == 1) return s.get(n / 2);
        return (s.get(n / 2 - 1) + s.get(n / 2)) / 2.0;
    }
}

Trivial to write; far too slow when queries are frequent.

BetterSorted List + Binary-Search Insert

Time O(n) add, O(1) findSpace O(n)

Keep the list always sorted: binary-search the insertion point (O(log n)) and insert there. The search is fast, but ArrayList.add(i, x) shifts the tail, so an insert is O(n). Queries become O(1) index reads.

Java

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

    public void addNum(int num) {
        int lo = 0, hi = sorted.size();
        while (lo < hi) { // first index with value >= num
            int mid = (lo + hi) >>> 1;
            if (sorted.get(mid) < num) lo = mid + 1;
            else hi = mid;
        }
        sorted.add(lo, num);
    }

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

Great for query-heavy streams; inserts still linear due to shifting.

OptimalTwo Heaps (Max-Heap Low, Min-Heap High)

Time O(log n) add, O(1) findSpace O(n)

low (max-heap) holds the smaller half, high (min-heap) the larger half, with every value in low ≤ every value in high and low holding equal or one more element. Insert on the correct side, then move one top across if the sizes drift. The median is low.peek() or the average of both tops.

Java

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

    public void addNum(int num) {
        if (low.isEmpty() || num <= low.peek()) low.offer(num);
        else high.offer(num);
        // rebalance: low may hold at most one extra element
        if (low.size() > high.size() + 1) high.offer(low.poll());
        else if (high.size() > low.size()) low.offer(high.poll());
    }

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

Logarithmic inserts, constant-time median — the standard answer.

Pro tip

Follow-up: if all values lie in [0,100], keep a 101-slot count array and walk it to the middle — O(1) add, O(100) find.

At a glance

Level	Approach	Time	Space
Brute Force	Store All, Sort on Query	`O(1) add, O(n log n) find`	`O(n)`
Better	Sorted List + Binary-Search Insert	`O(n) add, O(1) find`	`O(n)`
Optimal	Two Heaps (Max-Heap Low, Min-Heap High)	`O(log n) add, O(1) find`	`O(n)`

Common pitfalls

Max-heap via (a, b) -> b - a — overflows for extreme ints; prefer reverseOrder().
Integer division (a + b) / 2 — loses the .5; divide by 2.0.
Balancing sizes only, without the order check — a big value can end up in low.

Interview tips

Draw the two halves as two triangles meeting at the median — heap tops face each other.
State both invariants (ordering and size) and show each addNum restores them.
Have the bucket-count answer ready for the bounded-range follow-ups.

Pattern

Two heaps → maintain a running median / k-th boundary of a dynamic multiset.

My notes saved in this browser