Sliding Window Median

Compute the median of every window of size k in a list of integers.

sliding-window median sorting list

Write a function `sliding_window_median(nums, k)` that takes a list of integers `nums` and a positive integer `k` (size of the sliding window). The function must return a list of floats, where the i-th element is the median of the subarray `nums[i : i+k]` for each valid start index `i`. The median of an odd-size window is the middle element when sorted; for an even-size window, it is the average of the two middle elements. All medians should be returned as floats. The order of the output must match the order of the windows.

Constraints

1 ≤ k ≤ len(nums) ≤ 10^3. Each element in nums is an integer in the range [-10^6, 10^6]. The solution must compute each window independently; O((n-k+1) * k log k) is acceptable for this scale, but more efficient approaches are welcome.

Example

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

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

For each window, create a sorted copy and pick the middle element(s).

Remember that for even k, average the two middle elements and return a float.

Sliding the window by one element changes only one removal and one addition—can you update the sorted window efficiently?

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.