# Leetcode: Sliding Window Median

Sliding Window Median

Similar Problems:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

```[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5
```

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,

```Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
1 [3  -1  -3] 5  3  6  7       -1
1  3 [-1  -3  5] 3  6  7       -1
1  3  -1 [-3  5  3] 6  7       3
1  3  -1  -3 [5  3  6] 7       5
1  3  -1  -3  5 [3  6  7]      6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
```

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/sliding-window-median
class Solution:
## Basic Ideas: two heap
## Complexity: Time O(n*k), Space O(k)
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
import heapq
l1, l2 = [], []
maxHeap = heapq.heapify(l1)
minHeap = heapq.heapify(l2)

res = []
for i in range(len(nums)):
heapq.heappush(l1, -nums[i])

if i<k-1: continue

# rebalancing
while len(l1) > len(l2):
heapq.heappush(l2, -heapq.heappop(l1))

# collect results
item = (-l1[0] + l2[0])/2 if k%2==0 else float(l2[0])
res.append(item)

# remove item
if self.heapRemove(l1, -nums[i-k+1]):
# Notice: If we delete from l1, move one back from l2 to l1
heapq.heappush(l1, -heapq.heappop(l2))
else:
self.heapRemove(l2, nums[i-k+1])
return res

def heapRemove(self, l, item):
k = -1
for i in range(len(l)):
if l[i] == item:
k = i
break
if k != -1:
l[k] = l[0]
heapq.heappop(l)
heapq.heapify(l)
return True
return False

## Basic Ideas: insert with binary search
## Complexity: Time O(n*k), Space O(k)
def medianSlidingWindow_v1(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
import bisect
res = []
window = sorted(nums[:k])
for a, b in zip(nums, nums[k:]+[0]):
res.append((window[int(k/2)] + window[~int(k/2)])/2)
window.remove(a)
bisect.insort(window, b)
return res
```

Share It, If You Like It.