Find Median from Data Stream
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Build a class with addNum(num) and findMedian() over a growing stream of numbers.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you stored everything sorted, where is the median? Do you need the rest of the order?
- Hint 2A max-heap for the lower half and a min-heap for the upper half give instant access to the two middle values.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A line of people ordered by height arriving one by one. You cut the line in two halves: the shorter half and the taller half. Only the two people at the cut matter: the tallest of the short half and the shortest of the tall half. Keep both halves the same size (or the short half one bigger) and the median is the person at the cut, or the average of the two at the cut.
- The obvious way
Insert into a sorted list each time (O(n) per add) or sort on each query.
- The key insight
Low is a max-heap, high is a min-heap. To add a number: push it into low, move low's biggest into high (so the numbers cross the cut properly), and if high becomes bigger than low move high's smallest back. Then low has the same size as high, or one more. Median = top of low (odd count) or the average of both tops (even count). O(log n) per add, O(1) per query.
- The algorithm
- Make low (max-heap) and high (min-heap).
- addNum: push into low, then move low's biggest into high.
- If high has more numbers than low, move high's smallest into low.
- findMedian: top of low, or the average of both tops.
Watch it run
Exampleadd 5, 2, 8, 1
Add 5: the lower half is {5}, the upper half is empty. Median 5.
low {5}, high {} -> 5Where people slip
- Divide by 2.0 (or 2 in Python 3 is fine) so an even count gives a decimal, not a truncated integer.
- Re-balance after every add so the sizes never differ by more than one.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import heapq
class MedianFinder:
def __init__(self):
self.low = [] # max-heap (negatives): the smaller half
self.high = [] # min-heap: the bigger half
def addNum(self, num):
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low)) # biggest of the small half crosses the cut
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high)) # keep low as big as high, or one bigger
def findMedian(self):
if len(self.low) > len(self.high):
return float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.