Sliding Window Median
Notion● HardFULLTIMEONSITE INTERVIEWProblem statement
Given an integer array nums and a window size k, return the median of every contiguous window of length k, from left to right.
For an odd-length window, the median is its middle sorted value. For an even-length window, it is the average of the two middle sorted values.
Function
medianSlidingWindow(nums: int[], k: int) → double[]Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7]k = 3return = [1.0,-1.0,-1.0,3.0,5.0,6.0]Sorting each length-three window exposes its middle value.
Example 2
nums = [1,2]k = 1return = [1.0,2.0]Each one-element window has that element as its median.
Example 3
nums = [1,4,2,3]k = 4return = [2.5]The two middle sorted values are 2 and 3.
Constraints
1 <= nums.length <= 50000-1000000000 <= nums[i] <= 10000000001 <= k <= nums.length