LeetCode 295 · Hard · Heap / Priority Queue

Find Median from Data Stream

Design a class that takes numbers one at a time with addNum and can report the median of everything added so far with findMedian, the mean of the two middle values when the count is even.

O(log n)addNum
O(1)findMedian
two heapsmax-heap low half · min-heap high half

add x, median · separated by ; or , · 1–14 calls, at most 10 adds · x from −99 to 99 · median needs at least one add

Calls pointer walks the calls · return value underneath

small max-heap · lower half

val
≤

large min-heap · upper half

class MedianFinder { private PriorityQueue<Integer> small; // max-heap private PriorityQueue<Integer> large; // min-heap public MedianFinder() { small = new PriorityQueue<>(Collections.reverseOrder()); large = new PriorityQueue<>(); } public void addNum(int num) { small.offer(num); if (!small.isEmpty() && !large.isEmpty() && small.peek() > large.peek()) { int val = small.poll(); large.offer(val); } if (small.size() > large.size() + 1) { int val = small.poll(); large.offer(val); } if (large.size() > small.size() + 1) { int val = large.poll(); small.offer(val); } } public double findMedian() { if (small.size() > large.size()) { return small.peek(); } if (large.size() > small.size()) { return large.peek(); } return (small.peek() + large.peek()) / 2.0; }}
call
—
val
—
small
[]
large
[]
returned
[]

Why it works

  1. Brute force keeps a sorted list: insert each number in place (O(n) shifting, or re-sort) and read the middle in O(1). With many adds that is O(n) per add.
  2. Split the numbers into a low half and a high half. Invariant after every add: every value in small ≤ every value in large, and their sizes differ by at most 1. Then the median is only ever at the top of one heap, or the mean of both tops.
  3. Cost: each add does at most three heap pushes and pops, O(log n). findMedian reads the roots, O(1). Space O(n).
  4. Pitfalls: PriorityQueue is a min-heap, so small needs Collections.reverseOrder() to keep its max at the root. Fix the order first (lines 10-11), then the sizes (lines 15 and 19): rebalancing an out-of-order pair would move the wrong value. And divide by 2.0, not 2: integer division would turn the mean of 2 and 3 into 2, not 2.5.
  5. Follow-ups: if every number is in 0..100, keep 101 counters and walk them, O(100) per query. Sliding Window Median (480) adds removals, usually with lazy deletion from both heaps.