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 is sorted, it supports efficient lookups by value or by index. When accessing values by index, the can be used as an .
