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.0
addNum(2) → stream: [1, 2] → median: 1.5
addNum(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.

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.

LeetCode 295 — Find Median from Data Stream