# Sliding Window Median

#### Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array `[1,2,7,8,5]`, moving window size k = 3. return `[2,7,7]`

At first the window is at the start of the array like this

`[ | 1,2,7 | ,8,5]` , return the median `2`;

then the window move one step forward.

`[1, | 2,7,8 | ,5]`, return the median `7`;

then the window move one step forward again.

`[1,2, | 7,8,5 | ]`, return the median `7`;

Challenge

O(nlog(n)) time

Solution: 用分别用两个heap来维护这个median结构，左边一个maxHeap，右边一个minHeap，在加上当中一个median数值，两个Heap的size差最多为1，即leftSize==rightSize||leftSize+1==rightSize.

```public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0 || nums.length < k) {
return result;
}
PriorityQueue<Integer> leftMaxHeap = new PriorityQueue<>(1, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
if (a < b) {
return 1;
} else if (a == b) {
return 0;
} else {
return -1;
}
}
});
PriorityQueue<Integer> rightMinHeap = new PriorityQueue<>();
int median = nums[0];
//init the two heaps for the first k elements
for (int i = 1; i < k; i++) {
median = addElement(nums, i, median, leftMaxHeap, rightMinHeap);
}
//start moving the window forward
for (int i = 1; i <= nums.length - k; i++) {
median = addElement(nums, i + k - 1, median, leftMaxHeap, rightMinHeap);
//remove nums[i-1]
median = removeElement(nums, i - 1, median, leftMaxHeap, rightMinHeap);
}

return result;
}

public int addElement(int[] nums, int index, int median,
PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
//the left heap can only be the same size as the right heap
//or left size + 1 = right size
if (leftMaxHeap.size() == rightMinHeap.size()) {
if (nums[index] < median) {
leftMaxHeap.offer(nums[index]);
rightMinHeap.offer(median);
median = leftMaxHeap.poll();
} else {
rightMinHeap.offer(nums[index]);
}
} else {
if (nums[index] <= median) {
leftMaxHeap.offer(nums[index]);
} else {
leftMaxHeap.offer(median);
rightMinHeap.offer(nums[index]);
median = rightMinHeap.poll();
}
}
return median;
}

public int removeElement(int[] nums, int index, int median,
PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
//the left heap can only be the same size as the right heap
//or left size + 1 = right size
if (leftMaxHeap.size() == rightMinHeap.size()) {
if (nums[index] == median) {
median = leftMaxHeap.poll();
} else if (nums[index] < median) {
leftMaxHeap.remove(nums[index]);
} else {
rightMinHeap.remove(nums[index]);
if (!leftMaxHeap.isEmpty()) {
rightMinHeap.offer(median);
median = leftMaxHeap.poll();
}
}
} else {
if (nums[index] == median) {
median = rightMinHeap.poll();
} else if (nums[index] <= median) {
leftMaxHeap.remove(nums[index]);
if (!rightMinHeap.isEmpty()) {
leftMaxHeap.offer(median);
median = rightMinHeap.poll();
}
} else {
rightMinHeap.remove(nums[index]);
}
}
return median;
}```
Share