The Sliding Window Method
The sliding window method is a common strategy for optimizing an algorithm. This article will use code examples in JavaScript, but the technique is applicable to most languages.
There are several clues that this is the technique you’ll want to use for a problem. They typically involve unsorted arrays. If you are looking for a contiguous subarray that adheres to certain guidelines, you’ll probably want to use a sliding window. Contiguous means all numbers in the subarray are touching, as in you are not skipping any numbers within the subarray to come up with the answer. For example:
const array = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];In this array, [‘a’, ‘b’, ‘c’] is a contiguous subarray, but [‘b’, ‘d’, ‘e’] is not, because ‘b’ does not touch ‘d’ in the original array.
We can further classify sliding windows as static window problems or dynamic window problems. In static window problems, you will always be looking at a subarray/substring of a specific length, ex: ‘Find the maximum sum of ‘k’ contiguous integers in an integer array.” Here, you will have a k-sized window that will stay k-sized throughout the problem. Let’s do this one together.
The brute force solution to the problem would be to add up k integers starting with the first element. Then, add up k integers starting with the second element. Then, add up k integers starting with the third element…until you reach the end of the array. Let’s see some pseudocode for what this involves:
let k = 5;
let array = [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6];//iterate from the first element, and on each iteration add the bold numbers together://first iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//second iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//third iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//fourth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//fifth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sixth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//seventh iteration:[1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]//return the maximum sum found
Can you see all of the overlap? This is what we will get rid of using the sliding window method.
In the sliding window method, instead of adding up k elements each time, we will keep track of the previous sum, slide the window over, and readjust the sum.
let k = 5;
let array = [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6];//iterate from the first element, and on each iteration add the bold numbers together://first iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = 1 + 5 + 3 + 6 + 8 = 23
//second iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 1 + 3 = 25 => here we have slid the window, so 1 is no longer a part, and 3 has been added. We subtract and add to reflect this.
//third iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 5 + 6 = 26
//fourth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 3 + 8 = 31
//fifth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 6 + 0 = 25
//sixth iteration: [1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 8 + 3 = 20
//seventh iteration:[1, 5, 3, 6, 8, 3, 6, 8, 0, 3, 6]
//sum = sum - 3 + 6 = 23//return the maximum sum found => 31
This solution gets rid of the overlap and gives us a linear solution with respect to the size of the input array! It may not seem that useful for problems where k is small, but imagine a scenario with an array of size 100 and a k of size 50. You are getting rid of so much overlap in that case!
Here is solution code for this in JavaScript:
function max_sub_array_of_size_k(k, arr) {
let maxSum = 0,
let windowSum = 0,
let start = 0;
for (let end = 0; end < arr.length; end++) {
windowSum += arr[end];
if (end >= k - 1) {
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[start];
start--;
}
}
return maxSum;
}Next, lets talk about what I have been calling dynamic window problems. This method feels similar to two pointer methods, but instead of just caring about each pointer, you care about everything between the pointers! An example of this would be: “Find the length of the smallest contiguous subarray with a sum greater than or equal to a given value”,
In this case, we are checking different window lengths. For the brute force solution, we would start with index 0 and add subsequent indexes until we have reached the sum. Then we would start at index 1 and do the same thing, until we reach the end of the array. This is inefficient for the same overlapping reason we had before!
Instead, we want to start the window on the first element, and expand the window until we reach the sum. Then, we shrink the window by moving the start of the window ahead. Once we are lower than the sum, we have to expand the window again by moving the end of the window ahead! Let’s look at some pseudocode for this:
array: [1, 5, 3, 6, 8, 3]
sum: 10We start by setting the window to be length 1, looking only at the first element.
[1, 5, 3, 6, 8, 3]
1 is less than the sum, so we expand the window until we are greater than or equal to the sum:
[1, 5, 3, 6, 8, 3] => length = 4, windowSum = 15
Now we shrink the window by moving the start and check if it's still greater than the sum
[1, 5, 3, 6, 8, 3] => length = 3, windowSum = 14
We update our min length to be 3!
[1, 5, 3, 6, 8, 3] => windowSum = 9
Now the sum is too small, so we expand our window again
[1, 5, 3, 6, 8, 3] => length = 3, windowSum = 17
We are big enough to shrink the window
[1, 5, 3, 6, 8, 3] => length = 2, windowSum = 14
Update our min length to be 2! Shrink the window.
[1, 5, 3, 6, 8, 3] => windowSum = 8
Too small, expand the window!
[1, 5, 3, 6, 8, 3] => length = 2, windowSum = 11
We have reached the end of the array, and the smallest window we saw that was greater than the test sum was 2 elements in length.
Go ahead and try to code this one out on your own! Good luck!
