Sliding Window Median

Question (LC.480)

Given a list of integers and a window size k, compute the medians of the all the sliding windows.

Example

I: [1,3,-1,-3,5,3,6,7], 4
O: [0.00000,1.00000,1.00000,4.00000,5.50000]

Window position                Median
---------------               -----
[1  3  -1 -3]  5  3  6  7       0.00
 1 [3  -1  -3 5]  3  6  7       1.00
 1  3 [-1  -3  5 3]  6  7       1.00
 1  3  -1 [-3  5  3 6]  7       4.00
 1  3  -1  -3 [5  3  6 7]       5.50 

Analysis

To maintain a sliding window, we need to support deletion. A balanced binary search tree is the easiest tool to use.

Code

from sortedcontainers import SortedList 


class Solution:
    
    
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        
        n = len(nums)
        
        results: List[float] = []
        
        if n == 0 or n < k:
            return results 
        
        
        sorted_list = SortedList()
        
        # initialization 
        
        for i in range(k-1):
            sorted_list.add(nums[i])
        
        # print(f'sorted_list: {sorted_list}')
        
        # extend the window
        for i in range(n - k + 1):
            # add the new element in the end of the window
            j = i + k - 1 
            sorted_list.add(nums[j])
            
            # compute median
            results.append(findMedian(sorted_list))
            
            # remove the old element in the front of the window 
            sorted_list.remove(nums[i])
            

        
        return results 

    
def findMedian(sorted_list: List[int]) -> float:
    n = len(sorted_list) 
    
    if n == 0:
        return 0

    if n % 2 == 1:
        return float(sorted_list[n // 2])
    else:
        return (sorted_list[(n // 2) - 1] + sorted_list[n // 2]) / 2.0
        

Time Complexity

For each window, adding is O(logk) finding median is O(logk) deleting is O(logk).

Because SortedList is sorted, it supports efficient lookups by value or by index. When accessing values by index, the SortedList can be used as an order statistic tree.