All problems

Find Median from Data Stream

Hard · heap

Numbers arrive one at a time. You are given them in arrival order as nums. After each number arrives, report the median of every number that has arrived so far, counting the new one.

The median of a group of numbers is the middle value once they are sorted. If the group has an even size there are two middle values, and the median is their mean, which can end in .5.

Return a list of the same length as nums, where entry i is the median of nums[0..i], as a decimal number (5.0, not 5). Repeated numbers all count. A number that arrives twice is two values in the group.

Examples

Example 1

Input: nums = [5, 2, 8]

Output: [5.0, 3.5, 5.0]

After 5 the group is {5}. After 2 it is {2, 5}, whose middle values are 2 and 5, so the median is 3.5. After 8 it is {2, 5, 8}, whose middle value is 5.

Example 2

Input: nums = [1, 2, 3, 4]

Output: [1.0, 1.5, 2.0, 2.5]

Example 3

Input: nums = [-4, -6]

Output: [-4.0, -5.0]

With both numbers in, the middle values are -6 and -4, and their mean is -5.

Constraints