Median from a data stream
HardStuck?
Show a hintHide the hint
Two heaps pointed at each other: the larger half's smallest, and the smaller half's largest. The median is at the tops.
The ideas behind this problem
Next in this lesson
The kth largest, without sorting everythingNumbers arrive one at a time. After each median request, report the median of everything seen so far.
With an even count the median is the mean of the two middle values. Sorting on every request is too slow: the intended solution keeps two heaps.
Constraints#
1 <= operations <= 200000-10^9 <= x <= 10^9- A
medianrequest never arrives before the firstadd.
Input
operations is a count then that many words, each add or median. values is a count then that many integers, one per operation, unused where the operation is median.
Output
One median per median operation, in order, each on its own line.
Examples
Input
5 add add median add median 5 1 2 0 3 0
Output
1.5 2.0
After 1 and 2 the median is their mean. Adding 3 makes it the middle value.
Input
3 add add median 3 5 5 0
Output
5.0
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.