The sliding window pattern

Depending on the problem at hand, there are patterns that we can follow to help us solve algorithm problems. The sliding window pattern creates a window which can be an array or number from one position to another. The sliding window pattern is very useful for keeping track of a subset of data in an array, string, etc. when the data is continuous in some way. Depending on a certain condition, the window increases or closes.

Recognizing the sliding window pattern

Again the sliding window pattern is very useful for keeping track of a subset of data. This will often be in an array and the data is continuous. The following is an example problem which can be solved using the sliding window pattern.

Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

Some example inputs look like this:
maxSubarraySum([1,2,5,2,8,1,5], 2) => 10
maxSubarraySum([1,2,5,2,8,1,5], 4) => 17
maxSubarraySum([4,2,1,6], 1) => 6


Solving the maxSubarraySum problem

The following solution is of the Time Complexity O(N). Many people may start out by teaching the naïve or "easy" solution. Instead, lets look at this solution which uses the sliding window pattern. If we can understand how this pattern works now, you will start to recognize other similar problems and you will be able to apply the sliding window pattern to those problems as well. You will also get a much better time complexity following this solution.

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if(arr.length < num) return null;
  for(let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i-num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

So, what is this solution doing?
First we are declaring two variables, maxSum and tempSum. These will be used a bit further down in our code. We have an if statement to check for any edge cases where the array is invalid. Num is the number with which we need to find the sum in our array. If the number is larger than the length of our array, we can't get a valid sum, and thus we return null.

Then, we create our first sum.
Let's take this example and pass in 3:
maxSubarraySum([2,6,9,2,1,8,5,6,3], 3)
We go to the beginning of our array and sum together the first 3 numbers(2, 6, and 9). We store the sum of these numbers in a variable, which we called maxSum. We then set our tempSum equal to maxSum(note we are returning maxSum at the end of the function). We now start another loop. Instead of starting at the beginning, or index 0, we start our loop after the first 3 numbers we already summed together. In this case, we would start at index 3(2).

Our tempSum is currently storing the value 17 (2+6+9), and we are going to add 2 (from index 4) and subtract 2(from index 0). If we check our sum again, we still have a value of 17. When we iterate through the loop again, we take our tempSum(17), add 1(index 5), and subtract 6(index 1). Our new tempSum is (9+2+1). The last line of our for loop takes the maximum value between maxSum and tempSum. If tempSum is larger than the value of maxSum, we overwrite maxSum's value. Otherwise, we continue looping.

Why does this solution work with O(N) time complexity?

We could have a million digits, or even millions of digits. The beauty of the sliding window pattern is that we only ever have to loop over our array one time.

Practice this question and solution. Then, start looking for more sliding window pattern problems. Give this one a shot:

Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer. This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.

Examples:
minSubArrayLen([2,3,1,2,4,3], 7) => 2 ([4,3] is the smallest subarray)
minSubArrayLen([4,3,3,8,1,2,3], 11) => 2