Sliding Window Median
Mastery
A window of size k slides over nums one position at a time. Return the median of each window: the middle value for an odd k, or the average of the two middle values for an even k, as decimals.
For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3 the answer is [1.0, -1.0, -1.0, 3.0, 5.0, 6.0].
The starter code sorts every window from scratch. It is correct but too slow when windows are large.
Examples
Example 1
Input:
median_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)
Output:
[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
Example 2
Input:
median_sliding_window([1, 2, 3, 4, 2, 3, 1, 4, 2], 3)
Output:
[2.0, 3.0, 3.0, 3.0, 2.0, 3.0, 2.0]
Constraints
1 <= k <= len(nums) <= 100000-10**9 <= nums[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetheapstwo-heaps-and-scheduling
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.