#295 Find Median from Data Stream
frequently reported atPayPalWalmartIntuitAmazonByteDance / TikTokApple
the problem
In plain words
Design MedianFinder with addNum(num) and findMedian() returning the median of all numbers added so far (average of the two middle values when the count is even).
in addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
out 1.5, 2.0
- -10⁵ ≤ num ≤ 10⁵
- At least one number before findMedian
- At most 5·10⁴ calls
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo heaps (median)
The median only needs the largest of the lower half and the smallest of the upper half. A max-heap and a min-heap keep exactly those two on top.
solutions
From brute force to optimal
Insert each number at its sorted position; read the middle.
- Binary-search the insertion point.
- ArrayList.add(pos, num).
- Median from the middle index/indices.
Insertion shifts up to n elements.
All numbers.
class MedianFinder { private final List<Integer> sorted = new ArrayList<>(); public void addNum(int num) { int pos = Collections.binarySearch(sorted, num); if (pos < 0) pos = -pos - 1; sorted.add(pos, num); // O(log n) to find, O(n) to shift } public double findMedian() { int n = sorted.size(); if (n % 2 == 1) return sorted.get(n / 2); return (sorted.get(n / 2 - 1) + (long) sorted.get(n / 2)) / 2.0; }}low = max-heap (smaller half), high = min-heap (larger half), |low| = |high| or |high| + 1.
- addNum: offer to low; move low's max to high; if high is bigger, move high's min back.
- findMedian: odd → low.peek(); even → average of both peeks.
At most five heap operations per add; median just peeks.
Every number lives in one heap.
class MedianFinder { private final PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap: smaller half private final PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap: larger half public void addNum(int num) { low.offer(num); // 1. drop it into the smaller half high.offer(low.poll()); // 2. the biggest of the small half moves up if (high.size() > low.size()) { // 3. keep low the same size or one bigger low.offer(high.poll()); } } public double findMedian() { if (low.size() > high.size()) return low.peek(); // odd count: the middle value return (low.peek() + (long) high.peek()) / 2.0; // even: average, overflow-safe }}Dry run
in the room
How to say it in the interview
talk track
- State the invariant (ordering + sizes) before coding; every line of addNum exists to restore it.
traps
- Averaging with int arithmetic:
(a + b) / 2truncates and can overflow — use(a + (long) b) / 2.0.
what they ask next
Follow-ups
All numbers are in [0, 100]?
Keep a count array of 101 buckets: add O(1), median by walking ≤ 101 buckets.
Sliding Window Median (LC 480)?
Two heaps plus removal of the element leaving the window — use lazy deletion (a map of pending removals) or two TreeMaps of counts.
before you submit
Edge cases to test
- One number: the median is that number.
- Even count: average the two tops as a double, widening to long first.
- Numbers arriving in sorted or reverse order: the rebalancing step keeps the sizes within one.
practise next
Similar problems
- #703Kth Largest Element in a StreamEasyin Heaps
- #4Median of Two Sorted ArraysHardin Binary Search