Find Median from Data Stream (LeetCode 295)
The median of a sorted list of numbers is its middle value; when the list has an even number of entries, the median is instead the average of the two values nearest the center.
- For example, the median of
[2,3,4]is3. - For example, the median of
[2,3]is(2 + 3) / 2 = 2.5.
Design a MedianFinder class that supports:
MedianFinder()— creates an emptyMedianFinder.void addNum(int num)— feeds the next integernumfrom an incoming stream into the structure.double findMedian()— returns the median of every number seen so far, accurate to within10^-5.
Worked Examples
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []][null, null, null, 1.5, null, 2.0]1 and 2, the median is (1 + 2) / 2 = 1.5. After adding 3, the numbers are [1, 2, 3] and the median is 2.0.⚖️Formal Constraints & Bounds
-105 <= num <= 105There will be at least one element in the data structure before calling
findMedian.At most
5 * 104calls will be made toaddNumandfindMedian.
Core Insight
Splitting data across two heaps keeps the median continuously pinned at the tops of the two heaps.
Real-World Scenario & Production Applications
Financial high-frequency trading real-time bid-ask spread tracking and network QoS packet latency SLA monitoring.
Subproblems & Recurrence Decomposition3 Phases
Maintain small (max-heap of lower half numbers) and large (min-heap of upper half numbers). Invariant: every element in small is <= every element in large.
# Invariant: max(small) <= min(large)
# Size invariant: len(small) == len(large) (+ 1)Step-by-Step Execution Trace Table
| Step | Stream Value Added | small (Max-Heap) | large (Min-Heap) | Calculated Median |
|---|---|---|---|---|
| 1 | 5 | [5] | [] | 5.0 (odd count top of small) |
| 2 | 15 | [5] | [15] | (5 + 15) / 2 = 10.0 |
| 3 | 1 | [5, 1] | [15] | 5.0 (rebalanced) |
| 4 | 3 | [3, 1] | [5, 15] | (3 + 5) / 2 = 4.0 |
| 1 | small = max_heap (lower half) |
| 2 | large = min_heap (upper half) |
| 3 | def addNum(num): |
| 4 | push num to small |
| 5 | if top(small) > top(large): |
| 6 | move top(small) to large |
| 7 | move one top across so that small holds len(large) or len(large) + 1 values |
| 8 | def findMedian(): |
| 9 | if len(small) > len(large): |
| 10 | return top(small) |
| 11 | return the average of top(small) and top(large) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The median splits an ordered collection into two equal halves. To maintain this dynamically without full sorting on every insertion, we divide the data between two heaps: a max-heap (`small`) storing the lower half and a min-heap (`large`) storing the upper half. Maintaining the order invariant $\max(small) \le \min(large)$ and the balance invariant $|small| - |large| \in {0, 1}$ allows retrieving the median in $O(1)$ time while inserting in $O(\log N)$. ⚖️ The Analogy: A Seesaw With the Small Half on One Side, the Big Half on the Other
Picture every number seen so far sorted into two piles: a "small half" pile (holding the smaller-valued numbers) and a "large half" pile (holding the larger-valued ones). Keep the two piles balanced in size, differing by at most one. If they're balanced, the median is the average of the tallest card in the small pile and the shortest card in the large pile — both instantly visible on top of their respective piles. If one pile has exactly one extra card, that top card alone is the median.
🔑 The Key Idea in the Code
small is a max-heap (values negated, since Python's heapq is min-heap-only) so its top is always the largest of the small half; large is a plain min-heap so its top is always the smallest of the large half — together, those two values are always the two numbers straddling the true middle of the whole dataset.
Direct comparison without heap balancing: Pushing directly to a heap without rebalancing sizes. The two heaps
small(max-heap) andlarge(min-heap) must never differ in size by more than 1.Crossing heap boundaries (max of small > min of large): Pushing directly into
smallorlargecan violate the invariantsmall[0] <= large[0]. Always route incoming numbers through one heap to the other to preserve ordering.Float division on even size: When total count is even, median is
(-small[0] + large[0]) / 2.0. In Python 2 or typed languages, integer division(a + b) / 2truncates decimals.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Streaming data + continuous median retrieval.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule in addNum: push to small; if -small[0] > large[0], move that top to large; then rebalance so len(small) is len(large) or one more. findMedian reads -small[0] (odd count) or averages it with large[0] (even count).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
addNum: fix the order (-small[0] > large[0]) before the sizes. A size fix first can be undone by the order move, leavinglargeone longer thansmall.Integer division when computing average of two roots for even stream size.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Two Heaps: a max-heap small for the lower half and a min-heap large for the upper half, so the middle values are always the two tops. In addNum I push the number to small. Then I fix the order: if small's top is bigger than large's top, I move it across. Only after that do I fix the sizes, moving one top across so small has the same count as large or one more. The trap is doing those two fixes the other way round: a size fix first can be undone by the order move, leaving large one longer. findMedian reads small's top when the count is odd and averages both tops when it is even. addNum is
O(log N), findMedian isO(1), and the two heaps hold all N numbers,O(N)space."
Complexity & Mathematical Proof
O(log N) Add, O(1) Find
Look at the execution steps: Two balanced heaps: max-heap small (lower half) and min-heap large (upper half). Adding number costs O(log N) heap sift. Finding median reads heap roots in O(1) time.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1). Two heaps storing all N streamed elements total O(N) space.
Tadd = O(log N), Tfind = O(1)
Derivation Progression
O(log N) heap push
Pushes incoming value into appropriate half.
0 ≤ |small| - |large| ≤ 1
Rebalances heap sizes in O(log N) root transfer.
O(1) peek small[0] or (small[0] + large[0]) / 2
Extracts median in strict constant time.
Variable Definitions
Total number of numbers added to the stream so far
Memory Architecture & Bounds
O(1)
O(N) Two heaps storing N elements
O(1) Float median value
Boundary Best / Worst Cases
findMedian, addNum.
.
addNum.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find median from data stream", "addNum in O(log N)", "findMedian in O(1)". The median is the value splitting an ordered dataset into two equal halves. Maintaining a sorted array requires insertion. A Senior SWE immediately applies Two Balanced Heaps: a max-heap small storing the lower half, and a min-heap large storing the upper half.
Up to calls to addNum and findMedian. Time budget: strictly per insertion and per median lookup. Auxiliary space: across the two heaps.
small stores negated values, so read its top as -small[0]. The even-count median must be a float average of the two tops.
Core Algorithmic State Invariants
- Follow-Up: Every Value in [0, 100]
LeetCode's first follow-up bounds the values to [0, 100]. Then the heaps are not needed: keep a count per value (101 buckets) and a total. addNum is one increment, and findMedian walks at most 101 buckets to the middle position(s), so memory no longer grows with the stream.
- Follow-Up: 99% of Values in [0, 100]
The second follow-up lets 1% of values fall outside [0, 100]. With fewer than half the values on either side of the range, the median always lies inside it, so the 101 buckets still find it; values below 0 or above 100 only need to be counted, to know how far into the buckets the middle position is.
Find Median from Data Stream (LeetCode 295)
The median of a sorted list of numbers is its middle value; when the list has an even number of entries, the median is instead the average of the two values nearest the center.
- For example, the median of
[2,3,4]is3. - For example, the median of
[2,3]is(2 + 3) / 2 = 2.5.
Design a MedianFinder class that supports:
MedianFinder()— creates an emptyMedianFinder.void addNum(int num)— feeds the next integernumfrom an incoming stream into the structure.double findMedian()— returns the median of every number seen so far, accurate to within10^-5.
Worked Examples
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []][null, null, null, 1.5, null, 2.0]1 and 2, the median is (1 + 2) / 2 = 1.5. After adding 3, the numbers are [1, 2, 3] and the median is 2.0.⚖️Formal Constraints & Bounds
-105 <= num <= 105There will be at least one element in the data structure before calling
findMedian.At most
5 * 104calls will be made toaddNumandfindMedian.
Core Insight
Splitting data across two heaps keeps the median continuously pinned at the tops of the two heaps.
Real-World Scenario & Production Applications
Financial high-frequency trading real-time bid-ask spread tracking and network QoS packet latency SLA monitoring.
Subproblems & Recurrence Decomposition3 Phases
Maintain small (max-heap of lower half numbers) and large (min-heap of upper half numbers). Invariant: every element in small is <= every element in large.
# Invariant: max(small) <= min(large)
# Size invariant: len(small) == len(large) (+ 1)Step-by-Step Execution Trace Table
| Step | Stream Value Added | small (Max-Heap) | large (Min-Heap) | Calculated Median |
|---|---|---|---|---|
| 1 | 5 | [5] | [] | 5.0 (odd count top of small) |
| 2 | 15 | [5] | [15] | (5 + 15) / 2 = 10.0 |
| 3 | 1 | [5, 1] | [15] | 5.0 (rebalanced) |
| 4 | 3 | [3, 1] | [5, 15] | (3 + 5) / 2 = 4.0 |
| 1 | small = max_heap (lower half) |
| 2 | large = min_heap (upper half) |
| 3 | def addNum(num): |
| 4 | push num to small |
| 5 | if top(small) > top(large): |
| 6 | move top(small) to large |
| 7 | move one top across so that small holds len(large) or len(large) + 1 values |
| 8 | def findMedian(): |
| 9 | if len(small) > len(large): |
| 10 | return top(small) |
| 11 | return the average of top(small) and top(large) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The median splits an ordered collection into two equal halves. To maintain this dynamically without full sorting on every insertion, we divide the data between two heaps: a max-heap (`small`) storing the lower half and a min-heap (`large`) storing the upper half. Maintaining the order invariant $\max(small) \le \min(large)$ and the balance invariant $|small| - |large| \in {0, 1}$ allows retrieving the median in $O(1)$ time while inserting in $O(\log N)$. ⚖️ The Analogy: A Seesaw With the Small Half on One Side, the Big Half on the Other
Picture every number seen so far sorted into two piles: a "small half" pile (holding the smaller-valued numbers) and a "large half" pile (holding the larger-valued ones). Keep the two piles balanced in size, differing by at most one. If they're balanced, the median is the average of the tallest card in the small pile and the shortest card in the large pile — both instantly visible on top of their respective piles. If one pile has exactly one extra card, that top card alone is the median.
🔑 The Key Idea in the Code
small is a max-heap (values negated, since Python's heapq is min-heap-only) so its top is always the largest of the small half; large is a plain min-heap so its top is always the smallest of the large half — together, those two values are always the two numbers straddling the true middle of the whole dataset.
Direct comparison without heap balancing: Pushing directly to a heap without rebalancing sizes. The two heaps
small(max-heap) andlarge(min-heap) must never differ in size by more than 1.Crossing heap boundaries (max of small > min of large): Pushing directly into
smallorlargecan violate the invariantsmall[0] <= large[0]. Always route incoming numbers through one heap to the other to preserve ordering.Float division on even size: When total count is even, median is
(-small[0] + large[0]) / 2.0. In Python 2 or typed languages, integer division(a + b) / 2truncates decimals.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Streaming data + continuous median retrieval.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule in addNum: push to small; if -small[0] > large[0], move that top to large; then rebalance so len(small) is len(large) or one more. findMedian reads -small[0] (odd count) or averages it with large[0] (even count).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
addNum: fix the order (-small[0] > large[0]) before the sizes. A size fix first can be undone by the order move, leavinglargeone longer thansmall.Integer division when computing average of two roots for even stream size.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Two Heaps: a max-heap small for the lower half and a min-heap large for the upper half, so the middle values are always the two tops. In addNum I push the number to small. Then I fix the order: if small's top is bigger than large's top, I move it across. Only after that do I fix the sizes, moving one top across so small has the same count as large or one more. The trap is doing those two fixes the other way round: a size fix first can be undone by the order move, leaving large one longer. findMedian reads small's top when the count is odd and averages both tops when it is even. addNum is
O(log N), findMedian isO(1), and the two heaps hold all N numbers,O(N)space."
Complexity & Mathematical Proof
O(log N) Add, O(1) Find
Look at the execution steps: Two balanced heaps: max-heap small (lower half) and min-heap large (upper half). Adding number costs O(log N) heap sift. Finding median reads heap roots in O(1) time.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1). Two heaps storing all N streamed elements total O(N) space.
Tadd = O(log N), Tfind = O(1)
Derivation Progression
O(log N) heap push
Pushes incoming value into appropriate half.
0 ≤ |small| - |large| ≤ 1
Rebalances heap sizes in O(log N) root transfer.
O(1) peek small[0] or (small[0] + large[0]) / 2
Extracts median in strict constant time.
Variable Definitions
Total number of numbers added to the stream so far
Memory Architecture & Bounds
O(1)
O(N) Two heaps storing N elements
O(1) Float median value
Boundary Best / Worst Cases
findMedian, addNum.
.
addNum.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find median from data stream", "addNum in O(log N)", "findMedian in O(1)". The median is the value splitting an ordered dataset into two equal halves. Maintaining a sorted array requires insertion. A Senior SWE immediately applies Two Balanced Heaps: a max-heap small storing the lower half, and a min-heap large storing the upper half.
Up to calls to addNum and findMedian. Time budget: strictly per insertion and per median lookup. Auxiliary space: across the two heaps.
small stores negated values, so read its top as -small[0]. The even-count median must be a float average of the two tops.
Core Algorithmic State Invariants
- Follow-Up: Every Value in [0, 100]
LeetCode's first follow-up bounds the values to [0, 100]. Then the heaps are not needed: keep a count per value (101 buckets) and a total. addNum is one increment, and findMedian walks at most 101 buckets to the middle position(s), so memory no longer grows with the stream.
- Follow-Up: 99% of Values in [0, 100]
The second follow-up lets 1% of values fall outside [0, 100]. With fewer than half the values on either side of the range, the median always lies inside it, so the 101 buckets still find it; values below 0 or above 100 only need to be counted, to know how far into the buckets the middle position is.