All problems
Sliding Window Median with Two Heaps
Problem
Compute the median of every sliding window of size k.
nums is the array. Maintain a max-heap for the lower half of each window and a min-heap for the upper half, removing the element that leaves the window and rebalancing after every change. Odd windows return the middle value and even windows the average of the two middle values, as floats.
Return one median per window ([] when k is not positive or exceeds the array length).
Hint
Keep the lower half at most one element larger than the upper half.
Test cases
case 1
in: [[1,3,-1,-3,5,3,6,7],3]
expected: [1,-1,-1,3,5,6]
case 2
in: [[1,2],1]
expected: [1,2]
case 3
in: [[1,2,3,4],2]
expected: [1.5,2.5,3.5]
case 4
in: [[],3]
expected: []
case 5
in: [[5],1]
expected: [5]
Starter codePython
def sliding_window_median(nums, k):
# Your code here
pass5 test cases · run your code against them in the editor