# Easy O(nlogk) Python solution using 2 binary searches

• The idea is simple: after caching and sorting the first k numbers and get the first median, just continue to:

• remove the number leaving sliding window from cache; and
• insert the number entering sliding window into cache and keep it sorted.

Since the cache is sorted, both steps can be done by binary search.

``````class Solution(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
cache = sorted(nums[:k])
# get first median
ans = [float(cache[k/2]+cache[~(k/2)])/2]
for to_remove, to_insert in zip(nums[:len(nums)-k], nums[k:]):
# remove the number leaving sliding window from cache
idx = self.binSearchValue(cache, to_remove, 0, k-1)
del cache[idx]
# insert the number entering sliding window into cache and keep it sorted
idx = self.binSearchInterval(cache, to_insert, 0, k-1)
cache.insert(idx, to_insert)
# get median
ans.append(float(cache[k/2]+cache[~(k/2)])/2)
return ans

def binSearchValue(self, array, val, l, r):
if l==r:
return l
m = (l+r)/2
if val==array[m]:
return m
elif val<array[m]:
return self.binSearchValue(array, val, l, m-1)
else:
return self.binSearchValue(array, val, m+1, r)

def binSearchInterval(self, array, val, l, r):
"""
I define the index of interval (returned value) as
array:    [  -2  0  2  ]
interval:  ↑0  ↑1 ↑2 ↑3
Extra care is needed when enumerating each case
"""
if l==r:
return l
if l==r-1:
if val<array[l]:
return l
else:
return r
m = (l+r)/2
if val>=array[m-1] and val<array[m]:
return m
elif val<array[m-1]:
return self.binSearchInterval(array, val, l, m-1)
else:
return self.binSearchInterval(array, val, m+1, r)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.