Running Median After Each Number in a Data Stream
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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`.
Overview: Numbers arrive one at a time from a stream; after each arrival, return the median of everything received so far, averaging the two middle values when the count is even. The problem tests keeping order statistics up to date efficiently as a data stream grows.
Numbers arrive one at a time from a data stream, in the order given by the integer list `nums`. After each number arrives, report the median of all numbers received so far. Return the list of these medians, one per arrival, in arrival order.
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.
### Rules
- `answer[i]` is the median of `nums[0]` through `nums[i]`, inclusive, so the returned list has exactly `len(nums)` entries.
- 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 (for example `3.5` or `-2.5`), so every value is exact; never round or floor it.
- No value here exceeds 2^31 - 1 in magnitude: the inputs and the sum of the two middle values (at most 2 * 10^5 in magnitude) all fit in a 32-bit integer.
### Constraints
- `1 <= len(nums) <= 5 * 10^4`
- `-10^5 <= nums[i] <= 10^5`
### Example 1
```text
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
```text
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`.
Constraints
- 1 <= len(nums) <= 5 * 10^4
- -10^5 <= nums[i] <= 10^5
Examples
Input: ([5, 2, 8, 1],)
Expected Output: [5.0, 3.5, 5.0, 3.5]
Explanation: Source Example 1: sorted prefixes 5 | 2,5 | 2,5,8 | 1,2,5,8 give 5, (2+5)/2, 5, (2+5)/2.
Input: ([-3, -3, 4],)
Expected Output: [-3.0, -3.0, -3.0]
Explanation: Source Example 2: both copies of -3 count, so the two middle values after two arrivals are -3 and -3.
Hints
- Each answer depends only on the one or two values in the middle of the sorted prefix, and one arrival moves that middle by at most half a position; think about what you can keep between arrivals instead of re-sorting up to 5 * 10^4 numbers each time.
- For an even count, average the two middle values with true division: a middle pair of -3 and -2 must give -2.5, not -3 or -2.
- Equal values are separate numbers, so never collapse duplicates when locating the middle.