Abhishek Jain

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.

// Header files for C++ Programs.
#include<bits/stdc++.h>
using namespace std;

// A function to calculate maximum sum of subarray
//of size m in an array of size n.

int findMaximumSum(int arr[], int n, int m)
{
	int max_result = INT_MIN;

	for (int i = 0; i <= n - m ; i++) {
		int running_sum = 0;
        for (int j = i; j < i+m && j < n; j++)
            running_sum = running_sum + arr[j];
            
		// Update the max_result variable.
		max_result = max(running_sum, max_result);
	}

	return max_result;
}

int main()
{
    int n = 5;
	int arr[n] = { 10, 20, 10, 30, 5 };
	int m = 3;
    int answer = findMaximumSum(arr, n, m);
    cout<<answer;
	return 0;
}

Output

60

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.

// Header files for C++ Programs.
#include <bits/stdc++.h>
using namespace std;

/* A function to calculate maximum sum of subarray
of size m in an array of size n using sliding window technique.
*/
int findMaximumSum(int arr[], int n, int m)
{

// calculate the sum of first m elements of that array
// and store that sum in a variable named running_sum.
	int max_result = 0;
	for (int i = 0; i < m; i++)
		max_result += arr[i];

	// Calculate sum of the remaining windows by
	// summing up the next element subtracting the
	// previous element.
	int running_sum = max_result;
	for (int i = m; i < n; i++) {
		running_sum = running_sum + (arr[i] - arr[i - m]);
		max_result = max(max_result, running_sum);
	}

	return max_result;  
}

int main()
{
	int n = 5;
	int arr[n] = { 10, 20, 10, 30, 5 };
	int m = 3;
    int answer = findMaximumSum(arr, n, m);
    cout<<answer;
	return 0;
}

Output

60

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

Conclusion

  • The use of the Sliding Window Algorithm is very much concentrated,i.e. where the size of the window for calculation of any problem or analysis of an algorithm is fixed throughout the program. Then the complexity can be reduced by this technique and the naive algorithm can be optimized with the help of the Sliding Window Technique.
  • The Time Complexity of running this Sliding Window technique algorithm is O(N) where N is the number of elements present.
  • It should always be applied when the size of the window is fixed.
  • We can implement this algorithm in many ways based on our convenience and the requirement of the problem like iterating from left to right or right to left, etc.

Author