Find Median from Data Stream
On this page
Problem statement
Numbers arrive one at a time. After any of them, you may be asked for the median of everything seen so far. Implement
addNum(num)andfindMedian(). With an odd count the median is the middle value; with an even count it is the average of the two middle values.
A short question with a classic answer: two heaps that split the data in half. It shows up as "running median of latencies" or "median price so far", and it is the base for Sliding Window Median. Original problem: LeetCode 295.
Example

addNum(5) findMedian() -> 5
addNum(15) findMedian() -> 10.0 # (5 + 15) / 2
addNum(1) findMedian() -> 5
addNum(3) findMedian() -> 4.0 # (3 + 5) / 2
addNum(8) findMedian() -> 5
Constraints (assumed)
- Up to 5 × 10⁴ calls in total; values fit in a 32-bit int.
findMedianis only called after at least oneaddNum.
What this question tests
- Seeing that you only need the middle, not the whole sorted order.
- Keeping two heaps with two invariants: order between them, and sizes within one of each other.
- Handling the even case without integer-division mistakes.
Questions to ask first
- How often is each method called? Mostly adds, mostly reads, or balanced?
- What range do the numbers have? A small fixed range allows counting instead of heaps.
- Return type for the even case? (Here: a float, the exact average.)
- Will numbers ever be removed? (Here: no. With removals this becomes Sliding Window Median.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.