Find Maximum in Sliding Window

Short Summary

In a large array of integers, find the maximum in a window of size w as the window slides through the array. Save each max in an end result array.

Example Diagram

I/O Example

inputArr = [8,2,4,-1,10,15];
windowSize = 3;

const outputArr = myFunction(inputArr, windowSize);

// outputArr -> [8,4,10,15];

Explanation and Walk-Through

We are given an array of integers (inputArr) and a window size (windowSize). Starting from the beginning of the inputArray we will move the window to the end 1 index at a time. We are asked to identify the max_value on every shift and record it to our result array.

Let's identify the important size factors:

inputArray.length -> N

Size of input array is important because it affects the amount of shifts we need to make.

windowSize -> W

Size of window is important because it is related with the amount of comparisons we need to make per shift.

Trying all possible combinations

Let's see how we can do this with simple thinking. We can start with tracking the window_start_index and window_end_index to keep track of our window. At every shift, we can increase these indexes by 1, until the window_end_index reaches the end of the input_array. This will allow us to cover all the inputArray from start to end.

At every shift, we can check the max value within our window and record it. Since we will shift our window 1 by 1, we will know the exact start and end indexes of our window. We can find the maximum of the current window by checking each item in the window.

Following this procedure will result in:

(N-W) window shifts *(W-1) comparisons per shift. Assuming N>>W and W>>1:

Our time complexity will be O(N*W).

Since at any given moment, we only need to keep track of the currentMaximum for the currentWindow, our space complexity will be constant. This is because size of our extra memory consumption does not increase with the size of N or W. We can always reuse the same memory space for keeping track of currentMax of currentWindow, and when we're done with it, we can save it and reuse the same memory space.

Our space complexity will be O(1);

function myFunction(inputArr, windowSize){
	const outputArr = [];
	let window_start_index = 0;
	
	for (; window_start_index + windowSize <= inputArr.length; window_start_index++ ){
		// Set the currentMax to the first element of the window
		let currentMax = inputArr[window_start_index];
		
		for (let i = 1; i<windowSize; i++ ){
			// i = 1 because we already have set the current max to the first element of the window
			let currentIndex = window_start_index + i;
			currentMax = currentMax > inputArr[currentIndex] ? currentMax : inputArr[currentIndex];
      		console.log(`temporary max ${currentMax}`)
		}
    
		outputArr.push(currentMax);
	}
	return outputArr;
}

Increasing efficiency

Let's see if we can improve our time complexity anymore. As one might see, we are making some extra comparisons as we move the window. The items that are not the first and not the last in a window have already been compared to a window maximum before, so we can omit those comparisons to improve the time efficiency.

Every time we move the window we only need to check two things:

Check if the currentMax is still in our current_window
Check if the new_coming_value is greater than the currentMax

When we follow this operation our overall process looks like the following:

We no longer have to keep track of the moving window, we can do our calculations as we go through the inputArr one by one. We still need to keep track of the maximum within a window and also we need to be able to compare the upcoming items as we move. To achieve that we can use a double ended queue (see dequeue or deque). Double ended queues allow us to add or remove items from both ends with O(1) time. We will use this feature to keep track of the currentMax and also if the currentMax is still within the window.

Our main strategy will be using this deque window as a quick server for 2 items that we are interested in:

currentMax -> this will be kept on the left most end of the deque.
secondMax -> this will be kept on the right end of the deque.

For the sake of efficiency we will keep the indexes of these items in our deque, so that we don't have to find their indexes again while checking if they are still in the window.

By repeating these over the inputArr, within N-W window shifts we can complete our operation. Assuming N>>W:

Our time complexity will be O(N).

We are using a deque with a capped max size of window size, and we are not generating any other side memory consumption on the way.

Our space complexity will be O(1).

Let's see how the could would look like.

function myEfficientFunction(inputArr, windowSize){
	const outputArr = [];
	let window_start_index = 0;
	
	let windowDeque = [];

	// Start with finding the max of the initial window.

	for(; window_start_index < windowSize ; window_start_index++){
		while(windowDeque.length > 0 && inputArr[window_start_index] >= inputArr[windowDeque[windowDeque.length -1]] ){
			windowDeque.pop();
		}
		windowDeque.push(window_start_index);
	}
	
	// Now we have the max of the initial window at the left most end of our deque
	// let's add it as our first result (remember we're holding indexes)
	outputArr.push(inputArr[windowDeque[0]]);
	// Now we can move on with the rest of our algorithms

	for(; window_start_index < inputArr.length; window_start_index++ ){
		while(windowDeque.length > 0 && inputArr[window_start_index] >= inputArr[windowDeque[windowDeque.length-1]] ){
      	// remove all the items smaller than currentMax
			windowDeque.pop();
		}
	
		if(windowDeque.length >0 && windowDeque[0] <= window_start_index-windowSize){
			// Our currentMax is not in the window anymore so let's drop it from out deque
			windowDeque.shift();
		}
	
		windowDeque.push(window_start_index);
	
		// Now we can add the currentMax to the result array
		outputArr.push(inputArr[windowDeque[0]]);
	}
	
	return outputArr;
}

Please comment or dm me if you have other questions or remarks.

Until next time,

Stay all in!

Reha S.

Jan 11 2021