Find Median from Data Stream
Hard · Heap & Counting · Two Pointers · Design · Sorting · Heap (Priority Queue) · Data Stream
Problem
Numbers arrive one at a time, and at any moment you may be asked for the median of everything seen so far: the middle value, or the average of the two middle values when the count is even. Build the class:
- MedianFinder() starts with no numbers.
- addNum(num) adds the integer num.
- findMedian() returns the median of all the numbers added so far, as a float.
Both calls should be fast, since there can be tens of thousands of each, in any order. With an even count the answer is often a half: the median of -1 and -2 is -1.5, and floor division would give -2. Medians of whole numbers are always whole or halves, so they are compared exactly.
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: MedianFinder(), addNum(1), addNum(2), findMedian(), addNum(3), findMedian() Output: 1.5, then 2.0
With 1 and 2 the two middle values average to 1.5. Once 3 arrives, the middle of 1, 2, 3 is 2.
Input: MedianFinder(), addNum(-1), addNum(-2), findMedian() Output: -1.5
The average of -1 and -2 is -1.5. Integer division, (-1 + -2) // 2, would round down to -2.
Constraints
- -10^5 <= num <= 10^5
- findMedian is only called after at least one addNum
- at most 5 * 10^4 calls to addNum and findMedian in total
Approaches
- A sorted list, with binary insertion — time O(n) addNum, O(1) findMedian, space O(n)
Follow-up
If every number in the stream lies in [0, 100], how would you optimize it? What if 99% of the numbers lie in [0, 100]?
Related problems
Start free on Cariara · Coding problems · System design studio
