480. Sliding Window Median

Practice Sliding Window Median for free on NudgeCode: Hard, Sliding Window pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

A window of size k slides over nums from left to right, one position at a time, so there are nums.length - k + 1 windows. Return the median of each window, in order.

The median of k numbers is the middle one after sorting them. When k is even, it is the average of the two middle numbers, which may not be an integer. Answers within 10^-5 of the true value are accepted.

Example

nums = [1,3,-1,-3,5,3,6,7], k = 3  ->  [1,-1,-1,3,5,6]
nums = [1,4,2,3], k = 2            ->  [2.5,3,2.5]

In the second case the windows are [1,4], [4,2] and [2,3].

Constraints

• 1 <= k <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1