Median of Every Window

A window of size k slides along a list of readings, one position at a time. Write window_medians(nums, k) that returns the median of every window, from left to right: a list of len(nums) - k + 1 numbers.

The median is the middle value of the window once it is sorted. When k is even there are two middle values, and here the median is the smaller of the two, so every answer is a number from the list.

Examples

window_medians([5, 1, 4, 2, 8, 3], 3)
# returns [4, 2, 4, 3]

window_medians([5, 1, 4, 2, 8, 3], 2)
# returns [1, 1, 2, 2, 3]

window_medians([7, 7, 7], 3)
# returns [7]

The first window is [5, 1, 4]. Sorted it reads [1, 4, 5], so its median is 4. With k = 2 the first window is [5, 1], and the smaller middle value is 1.

Constraints

• 1 <= k <= len(nums) <= 100,000
• Values are whole numbers between -10^9 and 10^9, and they can repeat
• Sorting every window from scratch is far too slow when k is in the thousands.