Sliding Window Maximum

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 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       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

The brute force method require us to search the w elements in the window every time we slide the window, and results to a O(wn) overall run time complexity, that is not desirable.

Of course, since we actually only cares the max element in the current window, so if we would know the max number of the previous window, we will be able to decide if we would like to replace the maximum. The heap data structure is perfect for this. We can put all the number within the window into a max heap. When sliding the window to the right, we simply remove the left element and add the right element. and that only takes log(w) time so the total complexity would be O(nlogw). Notice that to remove the element from the left, we need to keep track of the indices of the nodes.

Can we do better? Yes, we can solve this problem in O(n) time. We can have a (double queue) that contains only keeps next largest element in decreasing order.

Here is an example, if we have an array of 1, 2, 5, 3, 4, 1 and window width = 3. When we hit the number 5, the 1, and 2 will not be the max value in any circumstances so we can pop 1 and 2 out and the queue we have has only element 5, then 3 comes in and we push it into the queue. when 4 comes in for the next, the max number is 5, but before we put 4 into the queue, we pop 3 out because  3 will not be the max value of array that the window can cover.

import java.text.SimpleDateFormat;
import java.util.*;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;

public class Test {
	public static int[] windowMax(int [] array, int width) {
		Deque<Integer> doubleQueue = new LinkedList<Integer>();
		//calculate the first window max
		int [] maxArray = new int[array.length - width + 1];
		for (int i = 0; i < width; i++) {
			while(!doubleQueue.isEmpty() && array[i] > doubleQueue.peekLast())
				doubleQueue.removeLast();
			doubleQueue.push(array[i]);
		}
		maxArray[0] = doubleQueue.peekFirst();
		//then try to move the window right and pop 
		for (int i = width; i < array.length; i++) {
			if (doubleQueue.size() == width) // if full, remove the first max element
				doubleQueue.removeFirst();
			while(!doubleQueue.isEmpty() && array[i] > doubleQueue.peekLast())
				doubleQueue.removeLast();
			doubleQueue.addLast(array[i]);
			maxArray[i-width+1] = doubleQueue.peekFirst(); // first element will be the max;
		}
		return maxArray;
	}
	public static void main(String[] args) {
		Test t = new Test();
		int [] a1 = {30, 10, 50, '#', '#', '#', 20, 45, '#', '#', 36, '#', '#'};
		int [] a2 = {1,2,5,3,4};
		System.out.println(t. windowMax(a2, 3));
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s