Answer Running Median Queries Over a Stream of Inserted Integers

Integers arrive one at a time, and at any point you may be asked for the median of every integer received so far. Process a sequence of operations and return the answer to each median query.

Operation i is described by operations[i] and values[i]:

• "add": insert values[i] into the collection.
• "median": report the median of all integers inserted so far. For this operation values[i] is 0 and is ignored.

The median of the collection is its middle value after sorting in non-decreasing order. With an even count it is the arithmetic mean of the two middle values.

Function Signature

def median_stream(operations: list[str], values: list[int]) -> list[float]:

Rules

• Return one float per "median" operation, in the order those operations appear. If there are no "median" operations, return an empty list.
• Return every median as a float, including whole numbers (for example 10.0). Every median is exactly an integer or an integer plus one half, so no rounding is involved.
• Duplicate values count separately, and inserted values are never removed.

Constraints

• 1 <= len(operations) == len(values) <= 5 * 10^4
• Each operations[i] is exactly "add" or "median".
• -10^5 <= values[i] <= 10^5
• Every "median" operation is preceded by at least one "add" operation.

Examples

Example 1

• Input: operations = ["add", "add", "median", "add", "median"], values = [5, 15, 0, 1, 0]
• Output: [10.0, 5.0]
• Explanation: after inserting 5 and 15 the median is (5 + 15) / 2 = 10.0. After inserting 1 the sorted collection is [1, 5, 15], so the median is 5.0.

Example 2

• Input: operations = ["add", "median", "add", "median", "add", "add", "median"], values = [-4, 0, -4, 0, 7, 2, 0]
• Output: [-4.0, -4.0, -1.0]
• Explanation: at the three queries the sorted collections are [-4], [-4, -4] and [-4, -4, 2, 7]; the last median is (-4 + 2) / 2 = -1.0.