Sliding Window Algorithm

Sliding Window Algorithm is a technique for reducing the complexity of algorithms. It is used such that the need for reusing the loops gets reduced and hence the program gets optimized. In this technique, we reuse the result of the previous step to compute the result of the next step.

What is Sliding Window Algorithm?

It is an algorithm where we can fast compute the things which have a fixed window for calculation and we can fetch the result in an optimized manner than using the nested loops(naive approach). The main goal of this algorithm is to reuse the result of one window to compute the result of the next window.

Suppose there is a group of friends of 12 people and they decided to party together but the major concern is who is going to throw that treat. After a lot of discussion among them, they concluded that they are sitting at a round table and the group of three who is sitting adjacent to each other and have the sum of age of every member of that group is maximum among other groups of the same size will pay the bill.

So, to find that group the naive approach would be to consider every person and run a loop for the next three's sum of age but it would take O( 12*3 ) units here. We can use the sliding window technique and could reduce this problem from O(12*3) to O(12). In the next section, we will see how we can use the sliding Window technique to solve this problem.

How to Use Sliding Window Technique?

We can use the sliding window technique in the example mentioned above.

At first, we will add the sum of the age of three members and after that, we will keep adding the next one and subtracting the last one so that after every step we can get the sum of the age of three person and we keep comparing the sum. Here the window size is 3 and to compute next group age sum we slide the window. The time complexity of this algorithm is O(12) units and this whole algorithm is Sliding Window Algorith. Most of the sliding window problems can be solved using this algorithm, the portion here which slides every time is the sliding window.

Let's suppose,The students of different ages are:

[21, 23, 24, 22, 22, 21, 26, 23, 22, 21, 24, 20]

And the different windows of 3 people sitting adjacent to each other are - [21,23,24] , [23,24,22] , [24,22,22] , [22,22,21] , [22,21,26] , [21,26,23] , [26,23,22] , [23,22,21] , [22,21,24] , [21,24,20].

The sums here respectively are calculated using the sliding window technique, lets have a look how we approach this problem.

The sum of first three are 21+23+24 = 68, and the rest ones are 68-21+22 = 69, 69-23+22 = 68 and so on till last. Here, we can compare the sums calculated at each step to find the required answer.

Basic Steps to Solve Sliding Window Problems

The steps of using the Sliding window technique are as follows:

1. Find the size of the window on which the algorithm has to be performed.
2. Calculate the result of the first window, as we calculate in the naive approach.
3. Maintain a pointer on the start position.
4. Then run a loop and keep sliding the window by one step at a time and also sliding that pointer one at a time, and keep track of the results of every window.

Let's see how we can use these steps to solve sliding window problems. Suppose, we have an array of integers arr of n elements and we have to find the maximum sum of m elements in that array.

Example -

• We have n = 5, arr[5] = {10,20,10,30,5} and m = 3 Then the result would be 60 (20+10+30).

• We have n = 7, arr[7] = {2,10,17,1,9,13,4} and m = 4 Then the result would be 40 (17+1+9+13).

The naive approach to solve this problem is by running a loop for every element and then again a nested loop to calculate the sum of next m elements and after that maintaining the maximum at every step.

Naive Approach For Finding the Maximum Sum of M Consecutive Elements of An Array.

Output

And the time complexity of running this algorithm is O(n*m)

Optimized approach is implemented by using the Sliding Window Technique:

How can we compute the result by applying the sliding window technique :

• We calculate the sum of the first m elements of that array and store that sum in a variable named running_sum.
• Then we will run a loop linearly on the array till the end and slide the window and keep track of maximum_sum by comparing it with the running_sum every time.
• To get the sum of m elements every time for a window we will add the next element and subtract the first element and so on and keep increasing the first pointer also.
• This will give us maximum_sum every time.

Let's see through the program how the algorithm is implemented. Consider the same example as above.

Optimized Approach For Finding the Maximum Sum of M Consecutive Elements of An Array.

Output

In the above code, we are running a loop till m and calculating the sum of 1st window, after that linearly iterating over the whole array and add the next element and subtract the left element and after that maintaining the maximum at every step and moving the left by one unit every time. This algorithm is best optimized for solving this kind of problem where the window size is fixed.

Some of the practice problems related to this topic are mentioned below:-

1. Sliding Window Maximum
2. Subarray With Given Sum
3. Distinct Numbers in Window