Data Structures and Algorithms - Sliding Window Pattern
Published: 2022-05-23 13:37:44

So this one here is a pretty cool pattern to recognize and be able to implement.  Anytime you have a problem where it involves sub arrays you should always considering using this pattern.  First off anytime you can use a sliding window you can also brute force it with multiple for loops and conditionals.  So in a situation where you want to get something done you are more than welcomed to brute force all you'd like, however in most interviews or tech problems you would fail based on quadratic or exponential time complexity. When working with smaller sets you'd never realize just how long these take.  Let's look at this first type of problem where we want to return the longest substring without repeating characters.  I've seen this problem on LeetCode and I believe HackerRank, and I'm guessing there are many versions of this question out there.  It's a classic sliding window problem.  So lets look at this generic problem where we try to find the max consecutive sum of an array of numbers.  This method will take in an array, and number which is consecutive elements in the array.  Lets say we have the following array:
`[10,22,32,13,5,9]` and our number passed in looking for consecutive elements is 3.  

By using the brute force method we can do 2 for loops and we'd come up with the following arrays to add up and get a total and then compare:
```
[10,22,32]
[22,32,13]
[32,13,5]
[13,5,9]
```
And this approach will 100% work but it is definitely not an efficient way of solving this problem.  If we look at the first two arrays what are the differences?  Well in the first array we start with 10 and in the second array we end with 13, that means the 22 and 32 happen to be in both arrays and since they are why would we want to add them up again?  So in this case take our first sum which is 64 we'd subtract the first element (10) and add the next element (13) which would look like: 64 - 10 + 13, which would give us 67 which would be a new max value.  This is the idea of the sliding window.  We start with an initial window and then "slide" it over.  

So to make this work the first thing we'll have to do is get the very first sum of the subarray and in this case a simple for loop will work just fine.  I like to make a tempSum variable too so that I can use the Math.max() method and compare our maxSum to the tempSum (next window element) and see if we need to adjust out new total.  Now all we need to do is start a second loop starting at our consecutive number passed in and we now get our new tempSum which would be `tempSum - arr[i - num] + arr[i]` and if it's larger than the maxSum we'll store it.  So as you can see we never create new arrays we just use basic arithmetic to get the new sum and compare.  So here is my final function for it:
```
function maxSubarraySum(arr, num) {
    if(num > arr.length) return null;
    let maxSum = 0;
    let tempSum = 0;
    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 the first thing that you should always do with any type of coding problem is account for the edge case(s) which I do in the first line.  And there is the pattern!!!!!!!