https://leetcode.com/problems/sliding-window-median/

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.

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.

Note:

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

#### java

https://discuss.leetcode.com/topic/74724/java-solution-using-two-priorityqueues

Java solution using two PriorityQueues

Almost the same idea of Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream/

1. Use two Heaps to store numbers. maxHeap for numbers smaller than current median, minHeap for numbers bigger than and equal to current median. A small trick I used is always make size of minHeap equal (when there are even numbers) or 1 element more (when there are odd numbers) than the size of maxHeap. Then it will become very easy to calculate current median.
2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.

#### cpp

https://discuss.leetcode.com/topic/74963/o-n-log-k-c-using-multiset-and-updating-middle-iterator

Keep the window elements in a multiset and keep an iterator pointing to the middle value (to “index” k/2, to be precise). Thanks to @votrubac’s solution and comments.

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

O(n* log(n)) Time C++ Solution Using Two Heaps and a Hash Table

There are a few solutions using BST with worst case time complexity O(n*k), but we know k can be become large. I wanted to come up with a solution that is guaranteed to run in O(n* log(n)) time. This is in my opinion the best solution so far.

The idea is inspired by solutions to Find Median from Data Stream: use two heaps to store numbers in the sliding window. However there is the issue of numbers moving out of the window, and it turns out that a hash table that records these numbers will just work (and is surprisingly neat). The recorded numbers will only be deleted when they come to the top of the heaps.

Since both heaps will never have a size greater than n, the time complexity is O(n* log(n)) in the worst case.

https://discuss.leetcode.com/topic/74577/c-solution-o-n-k

C++ Solution O(n* k)

The idea is to maintain a BST of the window and just search for the k/2 largest element and k/2 smallest element then the average of these two is the median of the window.

Now if the STL’s multiset BST maintained how many element were in each subtree finding each median would take O(log k) time but since it doesn’t it takes O(k) time to find each median.

#### python

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

Easy Python O(nk)

Just keep the window as a sorted list.