# 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

# Lintcode: Data Stream Median

#### Data Stream Median

Numbers keep coming, return the median of numbers at every time a new number added.

Example

For numbers coming list: `[1, 2, 3, 4, 5]`, return `[1, 1, 2, 2, 3]`.

For numbers coming list: `[4, 5, 1, 3, 2, 6, 0]`, return `[4, 4, 4, 3, 3, 3, 3]`.

For numbers coming list: `[2, 20, 100]`, return `[2, 2, 20]`.

Challenge

Total run time in O(nlogn).

Clarification

What’s the definition of Median? – Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is `A[(n - 1) / 2]`. For example, if `A=[1,2,3]`, median is `2`. If `A=[1,19]`, median is `1`.

Solution: 维护两个堆 左边是max heap右边是min heap。当有新的数进来时先比较两个heap的数量 永远让left和right的size一样或者left比right多1， 这样的话median永远是left.poll()。然后确定好应该加到哪个heap之后，要比较当前数和两个堆顶数的大小，来决定是直接把该数放到那个heap中还是应该把另外一个heap的root放过来然后把这个数放到另外那个堆里。

O(NlogN) time.

```public int[] medianII(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int initialSize = 20;
int[] median = new int[nums.length];
Queue < Integer > leftHeap = new PriorityQueue < > (initialSize,
new Comparator < Integer > () {
public int compare(Integer a, Integer b) {
return b - a;
}
});
Queue < Integer > rightHeap = new PriorityQueue < > ();

for (int i = 0; i < nums.length; i++) {
if (leftHeap.size() > rightHeap.size()) {
//need to put this one to rightHeap
if (nums[i] >= leftHeap.peek()) {
rightHeap.offer(nums[i]);
} else {
rightHeap.offer(leftHeap.poll());
leftHeap.offer(nums[i]);
}
} else {
//need to put this one to leftHeap
if (leftHeap.isEmpty() && rightHeap.isEmpty()) {
leftHeap.offer(nums[i]);
} else {
if (nums[i] <= rightHeap.peek()) {
leftHeap.offer(nums[i]);
} else {
leftHeap.offer(rightHeap.poll());
rightHeap.offer(nums[i]);
}
}
}
median[i] = leftHeap.peek();
}
return median;
}```

# Heapify

Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?

• Heap is a data structure, which usually have three methods: push, pop and top. where “push” add a new element the heap, “pop” delete the minimum/maximum element in the heap, “top” return the minimum/maximum element.
What is heapify?
• Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
What if there is a lot of solutions?
• Return any of them.

Solution 1: For each of the node in the heap array, use siftup method once.

```public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = 0; i < A.length; i++) {
siftUp(A, );
}
}

public void siftUp(int[] A, int index) {
int parentIndex = (index - 1) / 2;
while (parentIndex >= 0 && A[index] < A[parentIndex]) {
swap(A, index, parentIndex);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}

public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}```

Solution 2. for A[0, …, n/2-1] non leaf nodes, call siftDown method, O(n) time complexity.

```public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = A.length / 2 - 1; i >= 0; i--) {
siftDown(A, i);
}
}

public void siftDown(int[] A, int index) {
while (index < A.length) {
int smallest = index;
if (index * 2 + 1 < A.length && A[index * 2 + 1] < A[smallest]) {
smallest = index * 2 + 1;
}
if (index * 2 + 2 < A.length && A[index * 2 + 2] < A[smallest]) {
smallest = index * 2 + 2;
}
if (smallest == index) {
break;
}
swap(A, smallest, index);
index = smallest;
}
}

public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}```