Running Median After Each Number in a Data Stream

Numbers arrive one at a time from a data stream, in the order given by nums. After each number arrives, report the median of all numbers received so far. Return the list of these medians, one per arrival.

The median of an odd count of numbers is the middle value after sorting them; for an even count, it is the mean of the two middle values.

Function Signature

def running_medians(nums: list[int]) -> list[float]:

Rules

• answer[i] is the median of nums[0] through nums[i], inclusive.
• Equal values are separate numbers and each one counts.
• Return each median as a float. Every median is either a whole number or a whole number plus one half, so every value is exact.

Constraints

• 1 <= len(nums) <= 5 * 10^4
• -10^5 <= nums[i] <= 10^5

Examples

Example 1

Input: nums = [5, 2, 8, 1]
Output: [5.0, 3.5, 5.0, 3.5]

After four numbers the sorted values are 1, 2, 5, 8, and the median is (2 + 5) / 2 = 3.5.

Example 2

Input: nums = [-3, -3, 4]
Output: [-3.0, -3.0, -3.0]

Duplicates count separately: after two arrivals both middle values are -3, and after three the middle value is still -3.

Example 3

Input: nums = [1, 10, 2, 9]
Output: [1.0, 5.5, 2.0, 5.5]

After 1, 10 the median is 5.5; after 1, 2, 10 it is 2; after 1, 2, 9, 10 it is (2 + 9) / 2 = 5.5.