## 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 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``````
``` Copy The Code & Input x – + cmd nums = [1,3,-1,-3,5,3,6,7], k = 3 Output x – + 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 x – + cmd nums = [1,3,-1,-3,5,3,6,7], k = 3 Output x – + 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 x – + cmd nums = [1,2,3,4,2,3,1,4,2], k = 3 Output x – + 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(Comparer.Create((x, y) => y.CompareTo(x))); var leftCount = 0; var right = new SortedDictionary(); var rightCount = 0; var result = new List(nums.Length - k + 1); for (int i = 0; i < nums.Length; i++) { if (i >= k) { if (rightCount > leftCount) result.Add(right.Keys.First()); 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++; } } if (rightCount > leftCount) result.Add(right.Keys.First()); else result.Add((right.Keys.First() + left.Keys.First()) / 2.0); return result.ToArray(); } } } Copy The Code & Input x – + cmd nums = [1,2,3,4,2,3,1,4,2], k = 3 Output x – + cmd [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000] Demonstration ```
``` #478 Leetcode Generate Random Point in a Circle Solution in C, C++, Java, JavaScript, Python, C# Leetcode #481 Leetcode Magical String Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```