TL;DR
Two balanced heaps (max-heap lower half, min-heap upper half): O(log n) per addNum, O(1) per findMedian, O(n) space.
Approach 1 — Naive design: sort when asked
This is a design problem, so there is no classic brute force; the ladder starts at the most naive design that works: append every number to a list and sort it whenever the median is requested.
class MedianFinder:
def __init__(self) -> None:
self.nums: list[int] = []
def addNum(self, num: int) -> None:
self.nums.append(num)
def findMedian(self) -> float:
self.nums.sort()
n = len(self.nums)
mid = n // 2
if n % 2 == 1:
return float(self.nums[mid])
return (self.nums[mid - 1] + self.nums[mid]) / 2
Complexity: addNum O(1); findMedian O(n log n) (Timsort is fast on nearly-sorted data, but the worst case stands). Space O(n).
With up to 5 * 10^4 calls, alternating add/find gives roughly n^2 log n total work — far too slow.
Approach 2 — Sorted list with binary insertion
The insight: keep the list always sorted instead of re-sorting. Binary search (bisect.insort) finds the insertion point in O(log n); the median is then two index lookups. The cost hides in the insertion itself: shifting the tail of a Python list is O(n).
import bisect
class MedianFinder:
def __init__(self) -> None:
self.nums: list[int] = []
def addNum(self, num: int) -> None:
bisect.insort(self.nums, num)
def findMedian(self) -> float:
n = len(self.nums)
mid = n // 2
if n % 2 == 1:
return float(self.nums[mid])
return (self.nums[mid - 1] + self.nums[mid]) / 2
Walkthrough of the first example: addNum(1) → [1]; addNum(2) inserts after 1 → [1, 2]; findMedian(): n = 2, average of indices 0 and 1 → 1.5. Then addNum(3) → [1, 2, 3], findMedian() → element at index 1 → 2.0. ✓
Complexity: addNum O(n) due to element shifting (the search is O(log n)); findMedian O(1). Space O(n). Total O(n²) worst case for n adds — noticeably better, still not the target.
Approach 3 — Two heaps
The insight: the median never needs the halves internally sorted — only the boundary between them. Split the data into a lower half and an upper half, sizes equal or lower-half-one-larger. Then the median is either the max of the lower half or the average of (max of lower, min of upper). “Max of a growing set” is a max-heap; “min of a growing set” is a min-heap. A binary heap gives O(log n) insert and O(1) peek — Python’s heapq implements a min-heap, so the lower half stores negated values.
The insertion dance keeps both invariants (ordering across the boundary, sizes within 1) with at most three heap operations:
- Push the new number onto
small (lower half).
- Move the largest of
small over to large — this guarantees every element of small ≤ every element of large, even if the new number belonged in the upper half.
- If
large outgrew small, move the smallest of large back.
import heapq
class MedianFinder:
def __init__(self) -> None:
self.small: list[int] = [] # lower half, max-heap via negation
self.large: list[int] = [] # upper half, min-heap
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
moved = -heapq.heappop(self.small)
heapq.heappush(self.large, moved)
if len(self.large) > len(self.small):
back = heapq.heappop(self.large)
heapq.heappush(self.small, -back)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2
Walkthrough of addNum(1), addNum(2), findMedian(), addNum(3), findMedian():
| call | step 1–2 | step 3 rebalance | small (real values) | large |
|---|
addNum(1) | 1 → small → moved to large | large bigger → 1 back to small | {1} | {} |
addNum(2) | 2 → small; max(1,2)=2 → large | sizes 1/1, no move | {1} | {2} |
findMedian() | — | — | tie → (1 + 2) / 2 = 1.5 ✓ | |
addNum(3) | 3 → small; max(1,3)=3 → large | large 2 > small 1 → 2 back | {1, 2} | {3} |
findMedian() | — | — | small bigger → -small[0] = 2.0 ✓ | |
Complexity: addNum O(log n) (constant number of heap pushes/pops), findMedian O(1), space O(n). For n interleaved calls: O(n log n) total.
Well-known variant: if values are known to live in a tiny range (e.g. ages 0–100), a counting array of bucket frequencies gives O(1) add and O(range) median — worth mentioning as the classic follow-up answer, but the two-heap design is the general solution.
Common pitfalls
- Pushing directly onto whichever heap “looks right” and only fixing sizes — without routing through one heap you can violate the cross-heap ordering (an element in
small larger than one in large), silently corrupting the median.
- Forgetting the negation when reading from the max-heap (
-self.small[0]), or negating on push but not on pop.
- Integer division: the even-count median must be a float — use
/ 2, not // 2.
- Off-by-one in the size invariant: decide once that
small may be one larger than large (never the reverse) and make both the rebalance and findMedian agree with that convention.
Pattern takeaway
Two heaps facing each other — a max-heap for the lower part, a min-heap for the upper part, kept balanced — turn any “running middle/boundary statistic” into O(log n) updates with O(1) queries. The general rule: when you only ever read the frontier between two ordered groups, don’t maintain full order; maintain just the frontier with a heap on each side.