Intro to DSA — The Sliding Window Technique

image credit: welcomia on Getty Images/iStockPhoto

For the past few months, I’ve done quite a bit of personal study when it comes to coding. I have been studying the basics, but one of those things that coders should always know is Data Structures and Algorithms. During this time, I have been leet-coding and started to learn a sort of “algorithm” that had piqued my interest, which is the window sliding algorithm. Thankfully, now I have an opportunity to write about it.

You said coding…Window Sliding, huh?

The name is confusing I know, however, the window sliding algorithm is more of a technique for problem-solving. The idea behind the window sliding technique is to convert two nested loops into a single loop. This technique comes in handy when you need to keep track of adjoining sequences of elements. It’s used to find subarrays within an array that will satisfy the given conditions, usually when working with Strings or Numbers.

Ok.. so how do we use it?

We can use it by finding the size of the window, then compute the results. We would usually start from the beginning of the data structure, then use a loop to slide the window over by one continuously and compute the results window by window.

image credit

Finding the max sum of the array, using the sub-array length of K.

Here is a pretty common question we can use this technique with.

Let’s say we are given an array of numbers and we want to find the max sum of the subarray length, which I’ll call k here.

array = [1, 3, 4, 5, 2, 4 ,8 ,9]
k = 3;

Now the most naive way to solve this problem is to solve it by adding the length of k and comparing the two sums of the first three groups of numbers, to the next. We’d want something similar to this.

1 + 3 + 4 = 8..
3 + 4 + 5 = 12..
(8 < 12) so maxTotal = 12;
4 + 5 + 2 = 11..
(12 > 11) so maxTotal = 12;

Now, the brute force way we could solve this problem is to implement a code similar to this:

let arr = [1, 3, 4, 5, 2, 4 ,8 ,9]
let maxTotal = 0;
let currSum;
let k = 3;
for(let a = 0; a < arr.length - k; i++){
     currSum = 0;
     for(let b = a; b < a + k; b++){
       currSum += arr[j];
     }
     maxTotal = Math.max(maxTotal, currSum);
   }
return maxTotal;

While this way will get us to our answer, the calculation behind this is super slow. This kind of time complexity is something similar to O(n*k). Using Window Sliding, we can get the time to solve down to O(n) complexity.

A faster way we can get this down is that instead of adding up all 3 numbers at one time, we can just subtract the starting number and add the next ending one. That would look similar to something like this:

1 + 3 + 4 = 8...
8 - 1 = 7...
7 + 5 = 12...
(8 > 7) so maxTotal = 8;
(8 < 12) so maxTotal = 12; 

To implement this technique, we could implement something similar to this instead:

// We can use getSum to add up the total after the first addition of // indexes 0 through 2
const getSum = (arr, start, end) =>{
    let sum = 0;
    for(let a = start; a <= end; a++){
      sum+=arr[i];
    }
    return sum;
};
//Then this will run through and subtract ecah number before it, //and slide over and add the next one which is two over. 
let currSum = getSum(arr, 0, 2);
let maxTotal = currSum;
for(let a = 0; i <= arr.length - k; i++){
     currSum -= arr[i - 1];
     currSum += arr[i + 2];
     max total = Math.max(maxTotal, currSum);
}
// Then we get the maximum total!
return maxTotal;

Voila! We have a quicker way to solve this problem.

Oh! That’s kind of cool then.

Yeah, it is! However, the way we solved the first question is not the only type of Window Sliding.

There are two main types of window sliding. The one we used to solve the question above is using Fixed Window Sliding. There is also Dynamic Window Sliding. As the name might mention, Fixed Window Sliding is used when an array is a specified size. Dynamic Sliding will change the window slide as it moves through the array.

So while we can’t use this technique for everything, this should help with problem-solving when it comes to arrays, and getting the output as quickly as possible. If you’d like more information, I’d give this video a quick watch, as it goes over the fundamentals of this technique.

I hope this was a helpful informative article about window sliding! Happy Coding!