Find Median From Data Stream

Hard · Heap / Priority Queue

Design a data structure that supports adding integers one at a time from a stream and, at any point, reporting the median of all numbers added so far. Implement addNum to insert a new value, and findMedian to return the current median as a floating point number. If an even number of values have been added, the median is the average of the two middle values.

Examples

Input:  addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.0
Why:    After adding 1 and 2 the sorted list is [1,2] so the median is the average 1.5; after adding 3 the sorted list is [1,2,3] so the median is the middle value 2.0.

Input:  addNum(5), findMedian(), addNum(1), findMedian()
Output: 5.0, 3.0
Why:    With just [5] the median is 5.0; after adding 1 the sorted list is [1,5] so the median is the average 3.0.

Input:  addNum(-1), addNum(-2), addNum(-3), findMedian()
Output: -2.0
Why:    Sorted values are [-3,-2,-1], the middle one is -2.0.

Constraints

-10^5 <= num <= 10^5, findMedian is only called after at least one addNum call, up to 5*10^4 total operations

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Find Median From Data Stream

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Find Median From Data Stream. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.