Algorithm

Problem Name: 480. Sliding Window Median

The 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 values.

• For examples, if `arr = [2,3,4]`, the median is `3`.
• For examples, if `arr = [1,2,3,4]`, the median is `(2 + 3) / 2 = 2.5`.

You are given an integer array `nums` and an integer `k`. 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.

Return the median array for each window in the original array. Answers within `10-5` of the actual value will be accepted.

Example 1:

```Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
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
```

Example 2:

```Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
```

Constraints:

• `1 <= k <= nums.length <= 105`
• `-231 <= nums[i] <= 231 - 1`

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
List list;
double[] ans;
boolean isEven;

public double[] medianSlidingWindow(int[] nums, int k) {
list = new ArrayList < >();
ans = new double[nums.length - k + 1];
isEven = k % 2 == 0;

for (int i=0; i < k; i++) {
}

Collections.sort(list);
int idx = 0;
ans[idx++] = getMedian();

for (int i=k; i < nums.length; i++) {
removeElement(nums[idx - 1]);
int tempIdx = getBinarySearchIdx(nums[i]);

ans[idx++] = getMedian();
}

return ans;
}

private int getBinarySearchIdx(int num) {
if (list.size() == 0 || num  <  list.get(0)) {
return 0;
}
if (num > list.get(list.size() - 1)) {
return list.size();
}

int start = 0;
int end = list.size();

while (start  <  end) {
int mid = (start + end) / 2;

if (list.get(mid) < num) {
start = mid + 1;
}
else {
end = mid;
}
}

return end;
}

private void removeElement(int num) {
for (int i=0; i < list.size(); i++) {
if (list.get(i) == num) {
list.remove(i);
break;
}
}
}

private double getMedian() {
if (isEven) {
return (double) (list.get(list.size()/2) + list.get(list.size()/2 - 1)) / 2;
}
else {
return (double) list.get(list.size()/2);
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,3,-1,-3,5,3,6,7], k = 3

Output

cmd
[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const medianSlidingWindow = function(nums, k) {
const window = nums.slice(0, k).sort((x, y) => x - y)
const resultLen = nums.length - k + 1
nums.push(0)

function insert(arr, val) {
let i = 0
while (i < arr.length && arr[i] < val) {
i++
}
arr.splice(i, 0, val)
}

const medians = []
const rightIdx = (k / 2) >>> 0
const leftIdx = k + ~rightIdx
for (let i = 0; i  <  resultLen; i++) {
medians.push((window[leftIdx] + window[rightIdx]) / 2)
window.splice(window.indexOf(nums[i]), 1)
insert(window, nums[k + i])
}
return medians
}
``````
Copy The Code &

Input

cmd
nums = [1,3,-1,-3,5,3,6,7], k = 3

Output

cmd
[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def medianSlidingWindow(self, nums, k):
window = sorted(nums[:k])
medians = []
for a, b in zip(nums, nums[k:] + [0]):
medians.append((window[k//2] + window[~(k//2)]) / 2.)
window.remove(a)
bisect.insort(window, b)
return medians
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,2,3,1,4,2], k = 3

Output

cmd
[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0480_SlidingWindowMedian
{
public double[] MedianSlidingWindow(int[] nums, int k)
{
// SortedDictionary.Keys.First() is must faster than SortedDictionary.Keys.Last() (terraible implementation of .net)
var left = new SortedDictionary < long, int>(Comparer.Create((x, y) => y.CompareTo(x)));
var leftCount = 0;
var right = new SortedDictionary < long, int>();
var rightCount = 0;

var result = new List < double>(nums.Length - k + 1);
for (int i = 0; i  <  nums.Length; i++)
{
if (i >= k)
{
else result.Add((right.Keys.First() + left.Keys.First()) / 2.0);

if (right.ContainsKey(nums[i - k]))
{
right[nums[i - k]]--;
if (right[nums[i - k]] == 0) right.Remove(nums[i - k]);
rightCount--;
}
else if (left.ContainsKey(nums[i - k]))
{
left[nums[i - k]]--;
if (left[nums[i - k]] == 0) left.Remove(nums[i - k]);
leftCount--;
}
}

if (!right.ContainsKey(nums[i]))
right[nums[i]] = 1;
else
right[nums[i]]++;
rightCount++;

var minRight = right.Keys.First();
right[minRight]--;
if (right[minRight] == 0) right.Remove(minRight);
rightCount--;
if (!left.ContainsKey(minRight))
left[minRight] = 1;
else
left[minRight]++;
leftCount++;

if (rightCount  <  leftCount)
{
var maxLeft = left.Keys.First();
left[maxLeft]--;
if (left[maxLeft] == 0) left.Remove(maxLeft);
leftCount--;
if (!right.ContainsKey(maxLeft))
right[maxLeft] = 1;
else
right[maxLeft]++;
rightCount++;
}
}

else result.Add((right.Keys.First() + left.Keys.First()) / 2.0);

return result.ToArray();
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,2,3,1,4,2], k = 3

Output

cmd
[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]