> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/heap/sliding-window-median.md).

# Sliding Window Median

## Question ([LC.480](https://leetcode.com/problems/sliding-window-median/description/))

> 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 

```python
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&#x20;

For each window, adding is O(logk) finding median is O(logk) deleting is O(logk).&#x20;

> Because [`SortedList`](http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList) is sorted, it supports efficient lookups by value or by index. When accessing values by index, the [`SortedList`](http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList) can be used as an [order statistic tree](https://en.wikipedia.org/wiki/Order_statistic_tree).&#x20;