# Summary of Ideas and an accepting solution

• 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)

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
``````

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