Find Median from Data Stream

Hard#295two heaps

Build a class that gets numbers one at a time with addNum and, whenever findMedian is called, returns the median of all the numbers so far: the middle one for an odd count, the average of the two middle ones for an even count. Our example: addNum(5), addNum(8), findMedian(), addNum(2), addNum(1), findMedian(), addNum(9), findMedian() — the medians are 6.5, 3.5 and 5.

295 Find Median from Data StreamWalkthrough · 1×

Example: addNum gets 5, 8, 2, 1, 9, with findMedian() after the 8, the 1 and the 9. In the middle, low grows to the left and high to the right; their tops face each other.

addNum(x)58219low, max-heaphigh, min-heap——findMedian—
not added yetx, or the number being movedadded; in a heaptop of a heapmedian: tops read, value returned

MedianFinder() is created: init runs once

01/38
restart · back · play · step
Speed
1class MedianFinder:
2 function init():
3 low = empty max-heap // smaller half
4 high = empty min-heap // larger half
5 function addNum(x):
6 if low is empty or x <= max of low:
7 push x into low
8 else:
9 push x into high
10 if size of low > size of high + 1:
11 push (pop max from low) into high
12 else if size of high > size of low:
13 push (pop min from high) into low
14 function findMedian():
15 if size of low > size of high:
16 return max of low
17 return (max of low + min of high) / 2
state
x
–
low
–
high
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A number goes to low only if it is no bigger than the top of low, and a number moves only as a top. So everything in low stays at or below everything in high.
  2. After each addNum, low has the same size as high or one more. So the middle of the sorted numbers is right at the tops: the top of low, or the average of both tops.
  3. The 5 shows why both moves are needed: the 1 puts low two ahead and 5 goes to high; the 9 puts high ahead and 5 comes back.

Complexity

addNum: time O(log n), at most two pushes and one pop. findMedian: time O(1), it only reads the tops. Memory O(n) for all the numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.