Challenge
Values arrive one at a time. For each requested prefix length k, return the median of values[:k]. For odd k, use the middle sorted value; for even k, average the two middle values. Output medians in checkpoint order. Do not sort every queried prefix afresh.
Input and output contract
0 ≤ n ≤ 60,000; |value| ≤ 1,000,000; checkpoints is a strictly increasing list of at most 1,500 integers in 1..n. An empty checkpoint list returns []. Numeric answers use 1e-7 absolute or 1e-9 relative tolerance. Only requested checkpoints produce output, keeping results within the runner’s output budget.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from running_median; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log(n + 1)) time; O(n) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[5, 1, 9, 3], [1, 2, 4]]
Expected return
[5.0, 3.0, 4.0]
Arguments
[[-3, -1], [2]]
Expected return
[-2.0]
Arguments
[[], []]
Expected return
[]
Hint
Maintain a max-heap of the lower half and a min-heap of the upper half. Their sizes differ by at most one.
The worked solution unlocks after completion, or with Premium access.