**Solution**

**Sliding Window Median** https://leetcode.com/problems/sliding-window-median/

**Ideas**

- List to store the window : Maintain a sliding window and keep sorting it. O(NKLg(K))
- List to store the window: Maintain a sorted window. Add and remove elements from it to maintain sorted variant. O(NK).
- BST to store the window: Create a special BST where a node has size and frequency field. size refers to the number of nodes in its subtree. frequency is the number of occurences of the key. Then median is a rank() operation which is average case Log(K). Average case complexity: NKlog(K). Worst case complexity: O(NK).
- 2 Heaps to store the median: Online median algorithm can be used to tackle the incoming part of the stream. Removal can be lazy. Just store what needs to be removed in a hash-table. Check the top element of the heap to see if it is marked for removal before using it for median computation. O(N * lgN)

https://discuss.leetcode.com/topic/74679/o-n-log-n-time-c-solution-using-two-heaps-and-a-hash-table

https://discuss.leetcode.com/topic/74634/easy-python-o-nk

**List to store the window: O((n-k) * klg(k)). TLE**

- Brute force simple slides across all windows and reports the minimum.

```
class Solution(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
result = []
for i in range(0, len(nums)-k+1):
x = sorted(nums[i:i+k])
if len(x) % 2 == 0:
median = (x[(len(x)//2) - 1] + x[(len(x)//2)])/2.0
else:
median = x[len(x)//2]
result.append(float(median))
return result
```

**List to : Sorted List with O(nk). Accepted.**

- Maintain a sorted window. Use remove and bisect.insort() modules.

```
from bisect import insort
class Solution(object):
def get_median(self, x):
N = len(x)
median = (x[N//2 - 1] + x[N//2])/2. if N % 2 == 0 else x[N//2]/1.
return median
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
window = sorted(nums[:k])
result = []
result.append(self.get_median(window))
for i in range(k,len(nums)):
window.remove(nums[i-k])
insort(window, nums[i])
result.append(self.get_median(window))
return result
```