progress

~/problems / Heaps / Heaps and priority queues

Find Median from Data Stream

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or play this problem's boss fight .

Implement a class MedianFinder that receives numbers one at a time and can report the median of everything seen so far:

  • MedianFinder() starts empty.
  • add_num(x) records the integer x.
  • find_median() returns the median as a float: the middle value when the count is odd, or the average of the two middle values when it is even. It is only called after at least one add_num.
mf = MedianFinder()
mf.add_num(10)
mf.find_median()   # 10.0
mf.add_num(4)
mf.find_median()   # 7.0
mf.add_num(6)
mf.find_median()   # 6.0

⭐ Bonus: a speed test with 100,000 adds, each followed by a median query, earns a star with O(log n) per add_num and O(1) per find_median. Re-sorting on every query is too slow for it.

Show hint

Split the numbers seen so far into a lower half and an upper half. You only ever need the largest of the lower half and the smallest of the upper half, and the halves must stay balanced in size.

Topic: Heaps and priority queues. heapq: top-k, k-way merge, two heaps for a running median.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc