Algorithm Action: The Sliding Window Approach

Photo by Michael Dziedzic on Unsplash

Algos, algos, algos: the cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a set of articles titled Algorithm Action.

Today, we’re checking out a specific problem solving pattern known as the sliding window.

You Mean That Gwyneth Paltrow Movie?

Nope, that’s Sliding Doors. (It’s a good one!) The sliding window approach involves making a window, which can be an array or number from one position to another, that either increases or decreases in size depending on conditions that are triggered.

Using a sliding window is effective when needing to keep track of a subset of data in your dataset. Here’s a simple problem you might see that calls for the use of a sliding window:

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

maxSubarraySum([1,2,5,2,8,1,5], 3) // 15

As per the problem, the dataset above contains an array and a number. Our function will need to figure out which three consecutive numbers have the highest total possible. In this case, it’ll be the 5, 2, and the 8 for a max of 15, but how do we get to an answer?

function maxSubarraySum

While it’s valuable to review naive solutions for overall comprehension, they’re not as fast as this optimized solution, which clocks in at a time complexity of O(N).

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;
}

The above solution is more efficient because while there may be two loops written down, we only loop over the entire array once (with the second loop). This is in stark contrast to the naive solution, which has us looping over tp sum n elements for the length of the array minus n indexes.

That said, let’s break the above solution down:

function maxSubarraySum(arr, num) { 
    let maxSum = 0; 
    let tempSum = 0;

Instead of looping over the entire array, we’ll be keeping a two sums running, maxSum and tempSum. We’ll initialize those here.

if (arr.length < num) return null; 

This line is to represent our work preventing errors from edge cases.

for (let i = 0; i < num; i++) { 
        maxSum += arr[i]; 
    }
tempSum = maxSum;

Now we see our first loop, which simply sums the first three array elements (hence the i < num). That sum is then set to maxSum, which is then set to tempSum.

for (let i = num; i < arr.length; i++) { 
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum); 
    }

The second loop is the heart of this function. Up top I wrote that the naive solution is inefficient because it loops over the entire array multiple times. There’s no need to do this. Instead of summing the entire subset of numbers every time, we set tempSum to itself minus the first element in the set and and itself plus the next number in the set. This is why it’s called a sliding window solution!

maxSubarraySum([2,6,9,4,1,8,5,6,3], 3)
2 + 6 + 9 = 17
tempSum = 17 
17 - 2 + 4 = 19 

And then we use Math.max to set the larger number, then return maxSum. By the end of the function’s execution, you’ll get the correct answer in linear time. So good!

If you liked what you read, consider connecting or dropping me a line at nick.echev@gmail.com!