Median of Every Fixed-Length Sliding Window in an Integer Array

Given an integer array nums and a window length k, slide a window of exactly k consecutive elements across the array from left to right, one position at a time. For every window position, report the median of the k numbers currently inside the window.

The median of a window is its middle value after sorting the window in non-decreasing order. When k is odd it is the single middle element; when k is even it is the arithmetic mean of the two middle elements.

Function Signature

def window_medians(nums: list[int], k: int) -> list[float]:

Rules

• The first window covers nums[0..k-1], the second covers nums[1..k], and so on, so there are exactly len(nums) - k + 1 windows.
• Return the medians in window order: the median of the window that starts at index i is element i of the result.
• Return every median as a float, including whole numbers (for example 5.0). Every median is exactly an integer or an integer plus one half, so no rounding is involved.
• Duplicate values count separately: the window [2, 2, 9] has median 2.0.

Constraints

• 1 <= k <= len(nums) <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• Values span the full signed 32-bit range, so the sum of the two middle elements of an even-sized window can fall outside the 32-bit range (its magnitude can reach about 2^32). Compute the mean without 32-bit overflow. All values and sums stay well within ±2^53.

Examples

Example 1

• Input: nums = [4, 1, 7, 3, 8, 2], k = 2
• Output: [2.5, 4.0, 5.0, 5.5, 5.0]
• Explanation: the windows are [4, 1], [1, 7], [7, 3], [3, 8] and [8, 2], and each median is the mean of its two values.

Example 2

• Input: nums = [5, 2, 9, 2, 6], k = 3
• Output: [5.0, 2.0, 6.0]
• Explanation: the sorted windows are [2, 5, 9], [2, 2, 9] and [2, 6, 9].

Example 3

• Input: nums = [3, -1, 4, 10], k = 4
• Output: [3.5]
• Explanation: the only window sorts to [-1, 3, 4, 10], and the mean of 3 and 4 is 3.5.