Builds on Top-K Heap, which you haven’t finished yet.
Two Heaps (Running Median)
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.
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.Two Heaps
stream of numbers ➔ max-heap (lower) + min-heap (upper) ➔ O(1) median| 1 | import heapq |
| 2 | |
| 3 | class MedianFinder: |
| 4 | """Find Median from Data Stream: the median after every added number. |
| 5 | Time: O(log N) add, O(1) find | Space: O(N) |
| 6 | """ |
| 7 | def __init__(self): |
| 8 | self.small: list[int] = [] # Max-heap (negated numbers) -> lower half |
| 9 | self.large: list[int] = [] # Min-heap -> upper half |
| 10 | |
| 11 | def addNum(self, num: int) -> None: |
| 12 | # 1. Push to small First: |
| 13 | # Every new number lands in the lower half first; the order and size rules below correct it from there. |
| 14 | heapq.heappush(self.small, -num) |
| 15 | |
| 16 | # 2. Restore the Order Rule: |
| 17 | # If the largest of the lower half now exceeds the smallest of the upper half, move it across so every value in small stays at most every value in large. |
| 18 | if self.small and self.large and (-self.small[0] > self.large[0]): |
| 19 | val = -heapq.heappop(self.small) |
| 20 | heapq.heappush(self.large, val) |
| 21 | |
| 22 | # 3. Restore the Size Rule: |
| 23 | # Moving a value in step 2 can unbalance the counts, so fix it only after the order is already correct: len(small) must equal len(large) or be one more. |
| 24 | if len(self.small) > len(self.large) + 1: |
| 25 | val = -heapq.heappop(self.small) |
| 26 | heapq.heappush(self.large, val) |
| 27 | elif len(self.large) > len(self.small): |
| 28 | val = heapq.heappop(self.large) |
| 29 | heapq.heappush(self.small, -val) |
| 30 | |
| 31 | def findMedian(self) -> float: |
| 32 | # 1. Read the Middle From the Top(s): |
| 33 | # small always holds the extra value when the count is odd, so an odd total reads small's own top; an even total averages both tops. |
| 34 | if len(self.small) > len(self.large): |
| 35 | return float(-self.small[0]) # Odd count: the lower top is the middle |
| 36 | return (-self.small[0] + self.large[0]) / 2.0 # Even count: average both tops |
small is at most every value in large, and len(small) - len(large) is 0 or 1.Keep the lower half of the numbers in the max-heap small and the upper half in the min-heap large, so the middle values are always the two tops. Two rules make that true: every value in small is at most every value in large, and len(small) equals len(large) or is one more; then findMedian reads -small[0] alone, or averages -small[0] and large[0]. The trap is the order of fixes in addNum: push to small, move its top to large if it is bigger than large[0], and only then rebalance the sizes; fixing the sizes first lets the order fix unbalance them again.
See it run
Two Heaps on the stream 5, 15, 1, 3, 8, 7, step by step
num nonelen(small) 0len(large) 0median none
Each column is one index of the heap array. The top row is small, which stores negated numbers. The bottom row is large.
pushedthe value just pushed onto smallmovedthe value just moved to the other heaptopa heap top that findMedian reads
small and large are both empty. The numbers 5, 15, 1, 3, 8, 7 arrive one at a time.
Gotcha 1 of 4
- The trap
Gotcha 1: Fixing the sizes before the order in
addNumMistake# 3. Size rule first if len(self.small) > len(self.large) + 1: ... # 2. Order rule second if self.small and self.large and (-self.small[0] > self.large[0]): ...Fix# 2. Order rule first if self.small and self.large and (-self.small[0] > self.large[0]): ... # 3. Size rule second if len(self.small) > len(self.large) + 1: ...What happens: Every new number goes into
smallfirst. The order fix may then move the top ofsmallintolarge. That move changes both sizes. If the sizes were fixed before it, they can be out of balance again. ThenfindMedianreads the wrong tops.Example: Find Median from Data Stream (LC 295): add 1, 2, 3 and read the median after eachMistake: returns [1.0, 1.5, 1.5]Fix: returns [1.0, 1.5, 2.0]
- The rank you need is a fixed
kcounted from one end, as in Find the Kth Largest Integer in the Array (LC 1985), not the middle, which moves as numbers arrive. See Top-K Heap
Deep Dive
Why the two tops hold the median
Top-K Heap keeps one heap and evicts from its root. This card keeps two heaps and moves a value from the root of one to the other. The median is the middle of the sorted numbers. Sorting is not needed. It is enough to know which numbers are in the lower half, which are in the upper half, and the largest of the lower half and the smallest of the upper half.
small is a max-heap for the lower half. Python's heapq only builds min-heaps, so small stores negated numbers and -small[0] is its largest value. large is a min-heap for the upper half, so large[0] is its smallest value. Both roots are the two numbers next to the middle.
Two rules make the roots correct. The order rule says that every value in small is at most every value in large. The size rule says that len(small) equals len(large) or is one more. With these rules, an odd count has its middle value at small[0], and an even count has its two middle values at the two roots.
The board uses the stream 5, 15, 1, 3, 8, 7. The medians are [5.0, 10.0, 5.0, 4.0, 5.0, 6.0]. For the stream 1, 2, 3 of Find Median from Data Stream (LC 295), they are [1.0, 1.5, 2.0].
Why addNum fixes the order first and the sizes second
addNum always pushes the new number into small. This can break the order rule, because the new number can be bigger than large[0]. The order fix moves the root of small to large. This move changes the sizes: small loses one value and large gains one.
A size fix cannot undo an order fix, but an order fix can undo a size fix. So the order fix runs first, and the size fix runs second. The size fix moves a root from one heap to the other. A root of one heap is never on the wrong side of the other heap's root after the order fix, so the move keeps the order rule true.
On the board, the number 8 shows this. Before it, small holds 3 and 1, and large holds 5 and 15. After the push, small has 3 values and large has 2, so the size rule holds and a size check does nothing. But 8 is more than large[0] = 5. The order fix moves 8 to large. Now small has 2 values and large has 3. The size rule fails, and the size fix moves 5 back to small.
If the sizes were checked first, the size check would find nothing wrong, and the order fix would leave large with one value too many. The medians after 8 and 7 would be 4.0 and 4.0, not 5.0 and 6.0. The card gotcha shows the same fault on 1, 2, 3.
Reading the median, and the cost
findMedian reads at most two values. If len(small) > len(large), the count is odd, and the answer is -small[0]. Otherwise the count is even, and the answer is (-small[0] + large[0]) / 2.0. Use / and not //, because the median of 1 and 2 is 1.5.
findMedian is O(1). addNum does one push and up to two pops and pushes. Each of these is O(log N), so addNum is O(log N). The space is O(N), because every number is in one of the two heaps.
Two other ways are slower. Sorting all numbers at each query costs O(N log N) per query. Keeping a sorted list and inserting each number costs O(N) per insert, because the later items shift. The two heaps need only O(log N) per number.
A heap cannot remove an item from its middle. Sliding Window Median (LC 480) must remove the number that leaves the window. It uses the same two heaps plus lazy deletion: it records that a number is removed, and discards it when it reaches a root.
60-Second Pitch
"The median is the middle of the sorted numbers, so I need the largest of the lower half and the smallest of the upper half. I keep the lower half in a max-heap small, stored as negated numbers, and the upper half in a min-heap large. Every new number goes into small first. If the root of small is bigger than the root of large, I move that root across, so every lower value is at most every upper value. Then I check the sizes. small may hold at most one extra value, and I move one root across if they differ more. The order fix goes first, because it can change the sizes. findMedian returns -small[0] for an odd count, or the average of the two roots for an even count. Adding is O(log N), reading is O(1), and the space is O(N)."
Common Questions
- Why two heaps and not one?
One heap gives fast access to only one end, the smallest or the largest. The median is in the middle. The two heaps give fast access to the largest of the lower half and the smallest of the upper half, and these are the two middle values.
- What are the time and space complexities?
addNumisO(log N)because it does a constant number of heap pushes and pops.findMedianisO(1)because it reads at most two roots. The space isO(N), because all numbers are stored.- Why does
smallhold the extra value, and notlarge? It is a choice that makes
findMediansimple. If the count is odd, the middle is always-small[0]. Iflargeheld the extra value, the odd case would readlarge[0]. Both are correct if the code is consistent.- What changes for Sliding Window Median (LC 480)?
A number leaves the window, and a heap cannot remove an item from its middle. Keep a count of numbers that are waiting to be removed, and keep the sizes of the two halves as the number of valid values. Discard a removed number when it reaches a root.
- How is this different from a fixed rank, such as the k-th largest?
A fixed rank counted from one end needs one heap of size
k, as in Kth Largest Element in a Stream (LC 703). The median rank moves as numbers arrive, so the card needs two heaps that both grow.
SWE Reasoning
Spot it
- Numbers arrive one at a time, and the answer is asked after each one or at any time.
- The wanted value is the median, or a rank in the middle that moves as numbers arrive. A fixed rank from one end is Top-K Heap instead.
- Sorting at each query would be too slow, and a heap with one root is not enough because the answer is in the middle.
- The wording names a median, a running median or a balance point between two halves.
The invariant, step by step
smallholds the lower half as negated numbers.largeholds the upper half. Both start empty.addNum(num)pushes-numontosmall. The new number is in the lower half for now.- If
-small[0]is more thanlarge[0], the order rule fails. The root ofsmallmoves tolarge. Now every value insmallis at most every value inlargeagain. - If
len(small)is more thanlen(large) + 1, a root moves fromsmalltolarge. Iflen(large)is more thanlen(small), a root moves fromlargetosmall, negated. Now the sizes differ by 0 or 1, with the extra value insmall. - The size move takes a root, which is the closest value to the middle. So the order rule stays true.
findMedianreads-small[0]whensmallhas the extra value, and averages the two roots when the sizes are equal.
Traps
- Size fix before order fix. The order fix can unbalance the sizes again, and nothing fixes them. The medians become wrong. Fix the order first.
- A value moved from
largetosmallwithout a minus sign.smallstores negated numbers, so a positive value breaks its order. Useheappush(small, -val). - Reading
large[0]when the count is odd. The extra value is insmall. The middle is-small[0]. //in the even case. It drops the fraction, so the median of1and2becomes1. Use/ 2.0.- Reading a root of an empty heap. On the first number,
largeis empty. The order check testsself.largefirst, andfindMedianreadslarge[0]only when the count is even, so both heaps then have a value.
Practice
Builds on Top-K Heap, which you haven’t finished yet.
Two Heaps (Running Median)
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.
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.Two Heaps
stream of numbers ➔ max-heap (lower) + min-heap (upper) ➔ O(1) median| 1 | import heapq |
| 2 | |
| 3 | class MedianFinder: |
| 4 | """Find Median from Data Stream: the median after every added number. |
| 5 | Time: O(log N) add, O(1) find | Space: O(N) |
| 6 | """ |
| 7 | def __init__(self): |
| 8 | self.small: list[int] = [] # Max-heap (negated numbers) -> lower half |
| 9 | self.large: list[int] = [] # Min-heap -> upper half |
| 10 | |
| 11 | def addNum(self, num: int) -> None: |
| 12 | # 1. Push to small First: |
| 13 | # Every new number lands in the lower half first; the order and size rules below correct it from there. |
| 14 | heapq.heappush(self.small, -num) |
| 15 | |
| 16 | # 2. Restore the Order Rule: |
| 17 | # If the largest of the lower half now exceeds the smallest of the upper half, move it across so every value in small stays at most every value in large. |
| 18 | if self.small and self.large and (-self.small[0] > self.large[0]): |
| 19 | val = -heapq.heappop(self.small) |
| 20 | heapq.heappush(self.large, val) |
| 21 | |
| 22 | # 3. Restore the Size Rule: |
| 23 | # Moving a value in step 2 can unbalance the counts, so fix it only after the order is already correct: len(small) must equal len(large) or be one more. |
| 24 | if len(self.small) > len(self.large) + 1: |
| 25 | val = -heapq.heappop(self.small) |
| 26 | heapq.heappush(self.large, val) |
| 27 | elif len(self.large) > len(self.small): |
| 28 | val = heapq.heappop(self.large) |
| 29 | heapq.heappush(self.small, -val) |
| 30 | |
| 31 | def findMedian(self) -> float: |
| 32 | # 1. Read the Middle From the Top(s): |
| 33 | # small always holds the extra value when the count is odd, so an odd total reads small's own top; an even total averages both tops. |
| 34 | if len(self.small) > len(self.large): |
| 35 | return float(-self.small[0]) # Odd count: the lower top is the middle |
| 36 | return (-self.small[0] + self.large[0]) / 2.0 # Even count: average both tops |
small is at most every value in large, and len(small) - len(large) is 0 or 1.Keep the lower half of the numbers in the max-heap small and the upper half in the min-heap large, so the middle values are always the two tops. Two rules make that true: every value in small is at most every value in large, and len(small) equals len(large) or is one more; then findMedian reads -small[0] alone, or averages -small[0] and large[0]. The trap is the order of fixes in addNum: push to small, move its top to large if it is bigger than large[0], and only then rebalance the sizes; fixing the sizes first lets the order fix unbalance them again.
See it run
Two Heaps on the stream 5, 15, 1, 3, 8, 7, step by step
num nonelen(small) 0len(large) 0median none
Each column is one index of the heap array. The top row is small, which stores negated numbers. The bottom row is large.
pushedthe value just pushed onto smallmovedthe value just moved to the other heaptopa heap top that findMedian reads
small and large are both empty. The numbers 5, 15, 1, 3, 8, 7 arrive one at a time.
Gotcha 1 of 4
- The trap
Gotcha 1: Fixing the sizes before the order in
addNumMistake# 3. Size rule first if len(self.small) > len(self.large) + 1: ... # 2. Order rule second if self.small and self.large and (-self.small[0] > self.large[0]): ...Fix# 2. Order rule first if self.small and self.large and (-self.small[0] > self.large[0]): ... # 3. Size rule second if len(self.small) > len(self.large) + 1: ...What happens: Every new number goes into
smallfirst. The order fix may then move the top ofsmallintolarge. That move changes both sizes. If the sizes were fixed before it, they can be out of balance again. ThenfindMedianreads the wrong tops.Example: Find Median from Data Stream (LC 295): add 1, 2, 3 and read the median after eachMistake: returns [1.0, 1.5, 1.5]Fix: returns [1.0, 1.5, 2.0]
- The rank you need is a fixed
kcounted from one end, as in Find the Kth Largest Integer in the Array (LC 1985), not the middle, which moves as numbers arrive. See Top-K Heap
Deep Dive
Why the two tops hold the median
Top-K Heap keeps one heap and evicts from its root. This card keeps two heaps and moves a value from the root of one to the other. The median is the middle of the sorted numbers. Sorting is not needed. It is enough to know which numbers are in the lower half, which are in the upper half, and the largest of the lower half and the smallest of the upper half.
small is a max-heap for the lower half. Python's heapq only builds min-heaps, so small stores negated numbers and -small[0] is its largest value. large is a min-heap for the upper half, so large[0] is its smallest value. Both roots are the two numbers next to the middle.
Two rules make the roots correct. The order rule says that every value in small is at most every value in large. The size rule says that len(small) equals len(large) or is one more. With these rules, an odd count has its middle value at small[0], and an even count has its two middle values at the two roots.
The board uses the stream 5, 15, 1, 3, 8, 7. The medians are [5.0, 10.0, 5.0, 4.0, 5.0, 6.0]. For the stream 1, 2, 3 of Find Median from Data Stream (LC 295), they are [1.0, 1.5, 2.0].
Why addNum fixes the order first and the sizes second
addNum always pushes the new number into small. This can break the order rule, because the new number can be bigger than large[0]. The order fix moves the root of small to large. This move changes the sizes: small loses one value and large gains one.
A size fix cannot undo an order fix, but an order fix can undo a size fix. So the order fix runs first, and the size fix runs second. The size fix moves a root from one heap to the other. A root of one heap is never on the wrong side of the other heap's root after the order fix, so the move keeps the order rule true.
On the board, the number 8 shows this. Before it, small holds 3 and 1, and large holds 5 and 15. After the push, small has 3 values and large has 2, so the size rule holds and a size check does nothing. But 8 is more than large[0] = 5. The order fix moves 8 to large. Now small has 2 values and large has 3. The size rule fails, and the size fix moves 5 back to small.
If the sizes were checked first, the size check would find nothing wrong, and the order fix would leave large with one value too many. The medians after 8 and 7 would be 4.0 and 4.0, not 5.0 and 6.0. The card gotcha shows the same fault on 1, 2, 3.
Reading the median, and the cost
findMedian reads at most two values. If len(small) > len(large), the count is odd, and the answer is -small[0]. Otherwise the count is even, and the answer is (-small[0] + large[0]) / 2.0. Use / and not //, because the median of 1 and 2 is 1.5.
findMedian is O(1). addNum does one push and up to two pops and pushes. Each of these is O(log N), so addNum is O(log N). The space is O(N), because every number is in one of the two heaps.
Two other ways are slower. Sorting all numbers at each query costs O(N log N) per query. Keeping a sorted list and inserting each number costs O(N) per insert, because the later items shift. The two heaps need only O(log N) per number.
A heap cannot remove an item from its middle. Sliding Window Median (LC 480) must remove the number that leaves the window. It uses the same two heaps plus lazy deletion: it records that a number is removed, and discards it when it reaches a root.
60-Second Pitch
"The median is the middle of the sorted numbers, so I need the largest of the lower half and the smallest of the upper half. I keep the lower half in a max-heap small, stored as negated numbers, and the upper half in a min-heap large. Every new number goes into small first. If the root of small is bigger than the root of large, I move that root across, so every lower value is at most every upper value. Then I check the sizes. small may hold at most one extra value, and I move one root across if they differ more. The order fix goes first, because it can change the sizes. findMedian returns -small[0] for an odd count, or the average of the two roots for an even count. Adding is O(log N), reading is O(1), and the space is O(N)."
Common Questions
- Why two heaps and not one?
One heap gives fast access to only one end, the smallest or the largest. The median is in the middle. The two heaps give fast access to the largest of the lower half and the smallest of the upper half, and these are the two middle values.
- What are the time and space complexities?
addNumisO(log N)because it does a constant number of heap pushes and pops.findMedianisO(1)because it reads at most two roots. The space isO(N), because all numbers are stored.- Why does
smallhold the extra value, and notlarge? It is a choice that makes
findMediansimple. If the count is odd, the middle is always-small[0]. Iflargeheld the extra value, the odd case would readlarge[0]. Both are correct if the code is consistent.- What changes for Sliding Window Median (LC 480)?
A number leaves the window, and a heap cannot remove an item from its middle. Keep a count of numbers that are waiting to be removed, and keep the sizes of the two halves as the number of valid values. Discard a removed number when it reaches a root.
- How is this different from a fixed rank, such as the k-th largest?
A fixed rank counted from one end needs one heap of size
k, as in Kth Largest Element in a Stream (LC 703). The median rank moves as numbers arrive, so the card needs two heaps that both grow.
SWE Reasoning
Spot it
- Numbers arrive one at a time, and the answer is asked after each one or at any time.
- The wanted value is the median, or a rank in the middle that moves as numbers arrive. A fixed rank from one end is Top-K Heap instead.
- Sorting at each query would be too slow, and a heap with one root is not enough because the answer is in the middle.
- The wording names a median, a running median or a balance point between two halves.
The invariant, step by step
smallholds the lower half as negated numbers.largeholds the upper half. Both start empty.addNum(num)pushes-numontosmall. The new number is in the lower half for now.- If
-small[0]is more thanlarge[0], the order rule fails. The root ofsmallmoves tolarge. Now every value insmallis at most every value inlargeagain. - If
len(small)is more thanlen(large) + 1, a root moves fromsmalltolarge. Iflen(large)is more thanlen(small), a root moves fromlargetosmall, negated. Now the sizes differ by 0 or 1, with the extra value insmall. - The size move takes a root, which is the closest value to the middle. So the order rule stays true.
findMedianreads-small[0]whensmallhas the extra value, and averages the two roots when the sizes are equal.
Traps
- Size fix before order fix. The order fix can unbalance the sizes again, and nothing fixes them. The medians become wrong. Fix the order first.
- A value moved from
largetosmallwithout a minus sign.smallstores negated numbers, so a positive value breaks its order. Useheappush(small, -val). - Reading
large[0]when the count is odd. The extra value is insmall. The middle is-small[0]. //in the even case. It drops the fraction, so the median of1and2becomes1. Use/ 2.0.- Reading a root of an empty heap. On the first number,
largeis empty. The order check testsself.largefirst, andfindMedianreadslarge[0]only when the count is even, so both heaps then have a value.