The problem
Design a structure that receives numbers one by one and can return the median of all numbers so far at any time.
Input: add 5, 15, 1, 3, 8, 7 (asking for the median after each) Output: 5, 10, 5, 4, 5, 6
Picture it
Picture two waiting rooms. The left room holds the smaller half of people (tallest at the door, a max-heap), the right room the taller half (shortest at the door, a min-heap). We keep the rooms the same size (left may have one extra). The median is the person at the left door, or the average of the two people at the doors.
How to recognise it
- Numbers arrive one at a time, and at any moment you may be asked for the median (the middle value, or the average of the two middle values for an even count).
- Queries and insertions are mixed, so you cannot sort once and be done.
- The median needs the boundary between the smaller half and the larger half, not the full order.
- Up to 5 × 10^4 calls rule out a re-sort per query.
- "Track the middle of a changing collection" points to two heaps (trees stored in lists with O(log n) push and pop): a max-heap for the lower half and a min-heap for the upper half.
Start with brute force
Keep every number in a list. When the median is asked for, sort the list and read the middle.
class MedianFinderBrute:
def __init__(self):
self.nums = []
def add_num(self, x):
self.nums.append(x)
def find_median(self):
s = sorted(self.nums)
n = len(s)
if n % 2:
return s[n // 2]
return (s[n // 2 - 1] + s[n // 2]) / 2
Adding is O(1), but each query sorts up to n numbers: O(n log n). With 5 × 10^4 numbers, a sort is about 8 × 10^5 steps, and 2.5 × 10^4 queries make roughly 2 × 10^10 steps. Space is O(n).
From brute force to the idea
- Find the waste. To read the median you only need the largest of the lower half and the smallest of the upper half, yet the sort orders everything on every query.
- Split into two halves. Keep the smaller half in a max-heap
low(stored negated, becauseheapqis a min-heap) and the larger half in a min-heaphigh. Every number inlowis at most every number inhigh. - Keep the sizes balanced.
lowhas the same count ashigh, or one more. - Insert in a way that keeps both rules. Push
xintolow, then movelow's largest intohigh. This guarantees the largest of the lower half is not bigger than anything inhigh. Ifhighis now longer, move its smallest back intolow. - Read the median at the doors. Odd count: the front of
low. Even count: the average of the two fronts.
This is the key idea: two heaps meeting at the median, with O(log n) inserts and O(1) reads.
The key idea
Two heaps split the data into halves; rebalance after each insert. Add O(log n), median O(1).
Python solution
class MedianFinder:
def __init__(self):
self.low, self.high = [], [] # max-heap (negated), min-heap
def add_num(self, x):
heappush(self.low, -x)
heappush(self.high, -heappop(self.low))
if len(self.high) > len(self.low):
heappush(self.low, -heappop(self.high))
def find_median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | add_num O(1); find_median O(n log n) | O(n) |
| Two heaps (shown code) | add_num O(log n): three heap operations at most; find_median O(1) | O(n): every number lives in one of the heaps |
Edge cases
- One number:
lowhas it; the median is that number. - Two numbers: the average of both, as a float: 5 and 7 give
6.0. - Output types: an odd count returns the stored int (5), an even count returns a float (
10.0), because of/ 2. The problem accepts answers within 10^-5. - Duplicates (
5, 5, 5, 5): medians are 5, 5.0, 5, 5.0. - Negative numbers: work, because only the sign of the stored values is flipped.
- Example (5, 15, 1, 3, 8, 7): the medians are 5, 10.0, 5, 4.0, 5, 6.0.
- No numbers yet:
find_medianraisesIndexError. The problem promises at least one number before each query. - Imports: the snippet needs
from heapq import heappush, heappop.
Common mistakes
- Pushing straight into one heap and balancing only by size. Counts look fine but the halves overlap: adding 1, 2, 3 then gives 3 as the median instead of 2.
- Forgetting to negate when pushing to or reading from
low. - Using
//for the average and losing the .5. - Re-sorting a list inside
add_num, which makes the insert O(n log n).
Every number is an integer from 0 to 100. Support the same two operations without heaps. Describe your approach, then write it if you like.
Compare with our answer
With only 101 possible values, count how often each appears. To find the median, walk the counts from 0 upward until the running total reaches the middle rank.
class MedianFinderSmall:
def __init__(self):
self.counts = [0] * 101
self.n = 0
def add_num(self, x):
self.counts[x] += 1
self.n += 1
def _kth(self, r): # r-th smallest, counting from 1
for value, c in enumerate(self.counts):
r -= c
if r <= 0:
return value
def find_median(self):
lo = self._kth((self.n + 1) // 2)
hi = self._kth(self.n // 2 + 1)
return (lo + hi) / 2
Adding is O(1) and a query is O(101), which is O(1) in n. Space is O(101).
A strong answer mentions: a counting array indexed by value, finding the middle rank(s) by a cumulative scan, and that this beats heaps only because the value range is tiny.
1. A monitoring system receives one latency reading per second and must show the current median at any time. Which structure fits best?
Two balanced heaps give O(log n) per insert and O(1) per median. A sorted array costs O(n) per insert because of the shift, a single min-heap exposes only the minimum, and a hash map has no order to read the middle from.
2. Why does the shown add_num push x into low and then move one item to high, instead of choosing a heap by comparing x with the fronts?
The largest of low (after adding x) goes to high, so whichever of the two was larger ends up on the correct side. A rebalance step is still needed afterwards, and low still stores negated values.
3. A learner replaces the body of add_num with heappush(self.low, -x) followed by if len(self.low) > len(self.high) + 1: heappush(self.high, -heappop(self.low)). Which sequence exposes the bug?
Ascending input puts the largest numbers into low, so the third median comes out as 3 instead of 2. The other three sequences happen to produce the right answers with the buggy code: descending numbers and equal numbers never put a bigger value in low.
Score 60% or more and the lesson is marked complete.