Find Median from Data Stream
Find the running median as numbers arrive using a sorted array vs two heaps.
Find Median from Data Stream
Problem: Design a data structure that supports two operations:
addNum(num)— add a number from a stream.findMedian()— return the median of all numbers added so far.
Example:
addNum(1)→ stream:[1]→ median:1.0addNum(2)→ stream:[1, 2]→ median:1.5addNum(3)→ stream:[1, 2, 3]→ median:2.0
Note
The median is the middle value. With an odd count it's the exact middle; with an even count it's the average of the two middle values. The challenge is keeping it fast as numbers keep arriving.
How to Think About It
Starting point: Keep a sorted array. Binary search for the insertion point, shift elements, then read the middle. O(n) per insert, O(1) median. Too slow for a high-volume stream.
What does the median actually need? You only need two things: the maximum of the lower half and the minimum of the upper half. You don't need the full sorted order of either half.
The two-heap idea: Split all numbers into two halves — lower and upper. Use a max-heap for the lower half (root = largest of the lower half) and a min-heap for the upper half (root = smallest of the upper half). Both roots are always accessible in O(1).
Keeping them balanced: After every insert, ensure the two heaps differ in size by at most 1. If they drift, move the root of the larger heap to the smaller one.
Reading the median: If sizes are equal, average both roots. If one heap is larger, its root is the median.
Why this works: You never sort the full set. Each insert is O(log n) — one heap push plus possibly one cross-heap move. Each median query is O(1).
Brute Force — Sorted Array Insert
View Brute Force
Optimal — Two Heaps
View Optimal Solution
| Approach | addNum | findMedian | Space |
|---|---|---|---|
| Sorted Array Insert | O(n) | O(1) | O(n) |
| Two Heaps | O(log n) | O(1) | O(n) |
Note
The Two Heaps approach is the classic interview answer. It achieves O(1) median at all times with only O(log n) cost per insert.