Sliding window median of every k-length window

Given an integer array nums and a window size k, return the median of every contiguous window of length k, as the window slides one position at a time from left to right. For an odd k the median is the middle value; for an even k it is the average of the two middle values.

Interface

Unless you agree on a different interface with the interviewer, assume:

median_sliding_window(nums: list[int], k: int) -> list[float] — one median per window, in window order, as floats. Return [] when k is 0 or larger than len(nums).

Example

median_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)  ->  [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
median_sliding_window([1, 2, 3, 4], 2)                ->  [1.5, 2.5, 3.5]
median_sliding_window([2, 2, 2, 1], 2)                ->  [2.0, 2.0, 1.5]   # duplicates

Constraints

0 <= len(nums) <= 10^5; values are 32-bit signed integers, so the sum of two middle values can overflow 32 bits.
Target O(n log k) time and O(k) extra space besides the output.

Clarifying questions

How is the median defined for even k, and should it be a float?
Can values repeat? (Then removal must take out exactly one copy.)
Can k be larger than the array, or zero?
Do I return the medians or stream them one at a time?

What a strong answer covers

The brute force (sort each window, O(n k log k)) as the baseline.
Two heaps: a max-heap for the lower half and a min-heap for the upper half, sizes differing by at most one; the outgoing value is deleted lazily with a counter of pending deletions, and the heaps rebalance by their real sizes.
Alternatively a sorted container (or a sorted list with binary search for insert and remove), and the trade-off: simpler code, O(k) shifts per step in a plain list.
Correct handling of duplicates and of the overflow in (a + b) / 2.
Tests: k = 1, k = n, even k, all equal values.

Follow-ups

The sliding window mean (moving average from a stream) with a running sum and a queue.
The values arrive as a stream and you must emit each median as soon as its window is complete.
Return any percentile of the window, not just the median.