Find Median from Data Stream
Problem Statement
Design a class MedianFinder that holds a stream of integers and can report their median at any time.
MedianFinder()starts with no numbers.addNum(num)addsnumto the stream.findMedian()returns the median of every number added so far. With an odd count it is the middle number. With an even count it is the average of the two middle numbers, which can be a fraction such as 1.5.
The two methods can be called in any order, so findMedian must give the right answer right after every addNum.
A sequence of addNum(num) and findMedian() calls. Every findMedian() comes after at least one addNum.
For each findMedian(), the median as a double. addNum returns nothing.
The numbers 1 and 2 have median (1 + 2) / 2 = 1.5. After adding 3, the numbers 1, 2, 3 have median 2.
One number: its own value, −5. Then −5 and 10 have median (−5 + 10) / 2 = 2.5.
- • −10^5 ≤ num ≤ 10^5
- • There will be at least one element in the data structure before calling findMedian
- • At most 5 · 10^4 calls will be made to addNum and findMedian
- • Follow-up: If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
- • Follow-up: If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
addNum appends the number; findMedian copies, sorts and reads the middle
addNum finds the slot with binary search and inserts; findMedian reads the middle in O(1)
A max-heap for the lower half and a min-heap for the upper half; the two tops are the middle
addNum just appends the number to a vector. findMedian sorts that vector and reads the middle, exactly as in the first question. Adding is O(1), but every findMedian pays for a full sort.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Two Heaps translate into production architectures and low-level memory mechanics.