Introduction to Sliding Window Algorithm

Published in

AI Skunks

8 min readApr 20, 2023

by Krishnakanth Naik Jarapala,

The Sliding Window algorithm is a powerful technique for reducing the complexity of algorithms. This algorithm is used to optimize programs by reducing the need for reusing loops. The basic idea behind this algorithm is to reuse the results of the previous step to compute the results of the next step. In this article, we will explore the Sliding Window algorithm, provide examples of its applications, and offer steps for solving problems using this algorithm.

Understanding the Sliding Window Algorithm

The Sliding Window algorithm is a fast and efficient way to calculate values that have a fixed window for computation. It allows us to fetch results in an optimized manner, which is more efficient than using the naive approach of nested loops. The primary goal of this algorithm is to reuse the results of one window to compute the results of the next window.

Example of Sliding Window Algorithm

Suppose a group of 12 friends decided to party together, and the group of three friends who are sitting adjacent to each other and have the maximum sum of ages will pay the bill. 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, which would take O(123) units. However, we can use the Sliding Window technique to reduce this problem from O(123) to O(12).

Using the Sliding Window Technique

To use the Sliding Window technique, we can add the sum of the age of three members at first, and then we will keep adding the next one and subtracting the last one. After every step, we can get the sum of the age of three persons, and we keep comparing the sum. The window size here is three, and to compute the next group age sum, we slide the window. The time complexity of this algorithm is O(12) units, and the whole algorithm is the Sliding Window algorithm. Most of the Sliding Window problems can be solved using this algorithm, and the portion that slides every time is the sliding window.

Example of Using Sliding Window Algorithm

Let’s consider the example of students of different ages — [21, 23, 24, 22, 22, 21, 26, 23, 22, 21, 24, 20]. The different windows of three 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]. We can calculate the sums of these windows respectively using the Sliding Window technique. For example, the sum of the first three windows would be 21+23+24 = 68, and the rest ones would be calculated as 68–21+22 = 69, 69–23+22 = 68, and so on until the last window. We can compare the sums calculated at each step to find the required answer.

Steps to Solve Sliding Window Problems

The steps to use the Sliding Window technique are as follows:

Find the size of the window on which the algorithm has to be performed.
Calculate the result of the first window, as we calculate in the naive approach.
Maintain a pointer on the start position.
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.

Example of Using Sliding Window Algorithm to Solve 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 using the sliding window technique. Here are the basic steps to solve this problem:

Find the size of the window on which the algorithm has to be performed. In this case, the window size is m.
Calculate the sum of the first m elements of the array using a loop. This will give us the initial result.
Maintain a pointer on the start position of the window, which is the first element of the array.
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.
At every step, calculate the sum of the current window by subtracting the first element of the previous window and adding the next element of the current window.
Maintain the maximum sum found so far and return it as the final result.

Let’s see how we can use these steps to solve sliding window problems with the following examples:

Example 1:

Suppose we have an array arr of n = 5 elements: {10, 20, 10, 30, 5} and we have to find the maximum sum of m = 3 elements in that array using the sliding window technique.

We start by calculating the sum of the first m elements: 10 + 20 + 10 = 40.
We then slide the window by one step at a time and calculate the sum of the new window at every step:
From {10, 20, 10}, we slide to {20, 10, 30} and calculate the sum as 20 + 10 + 30 = 60.
From {20, 10, 30}, we slide to {10, 30, 5} and calculate the sum as 10 + 30 + 5 = 45.
We maintain the maximum sum found so far, which is 60, and return it as the final result.

Therefore, the maximum sum of m = 3 elements in the array arr is 60.

Example 2:

Suppose we have an array arr of n = 7 elements: {2, 10, 17, 1, 9, 13, 4} and we have to find the maximum sum of m = 4 elements in that array using the sliding window technique.

We start by calculating the sum of the first m elements: 2 + 10 + 17 + 1 = 30.

2. We then slide the window by one step at a time and calculate the sum of the new window at every step:

From {2, 10, 17, 1}, we slide to {10, 17, 1, 9} and calculate the sum as 10 + 17 + 1 + 9 = 37.
From {10, 17, 1, 9}, we slide to {17, 1, 9, 13} and calculate the sum as 17 + 1 + 9 + 13 = 40.
From {17, 1, 9, 13}, we slide to {1, 9, 13, 4} and calculate the sum as 1 + 9 + 13 + 4 = 27.
We maintain the maximum sum found so far, which is 40, and return it as the final result.

This problem can also be solved using the Sliding window algorithm. We can start by calculating the sum of the first m elements and store it as the maximum sum. Then, we can slide the window by one element at a time and calculate the new sum by adding the new element and subtracting the element that went out of the window. We can then compare the new sum with the maximum sum found so far and update it if the new sum is greater.

Using the sliding window technique, we can solve this problem in O(n) time complexity, which is much faster than the naive approach.

Code to Find the Maximum Sum of m Consecutive Elements of an Array using Naive Approach:

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 += arr[j];
        }
        max_result = max(max_result, running_sum);
    }
    return max_result;
}

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

# Output: 20

The Time Complexity of Naive Approach is O(n*m) but we can optimize it by using Sliding Window Algorithm.

Code to Find the Maximum Sum of m Consecutive Elements of an Array using Sliding Window Algorithm:

#include <bits/stdc++.h>
using namespace std;

/*
A function to calculate the maximum sum of subarray
of size m in an array of size n using the 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 max_result.
    int max_result = 0;
    for (int i = 0; i < m; i++)
        max_result += arr[i];

    // Calculate the sum of the remaining windows by
    // summing up the next element and 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] = { 20, 10, -10, 15, 5 };
    int m = 3;
    int answer = findMaximumSum(arr, n, m);
    cout << answer;
    return 0;
}

# Output: 20

The code above implements the sliding window technique to efficiently calculate the maximum sum of a subarray of size m in an array of size n.

Initially, the sum of the first window of size m is calculated by iterating over the first m elements of the array. Then, a loop is run from m to n-1 and at each iteration, the running sum is updated by adding the next element and subtracting the left element of the current window. The maximum sum seen so far is maintained and updated at each step by taking the maximum between the current running sum and the previous maximum sum. The left index of the window is incremented by one unit at each iteration.

This approach is highly optimized for solving problems where the window size is fixed, as it avoids recalculating the sum of overlapping windows and reduces the time complexity from O(n*m) to O(n).

Conclusion

The sliding window algorithm is a powerful technique to solve problems with fixed windows. It helps to reduce the complexity of algorithms and optimize the program. The algorithm can be used to solve a variety of problems such as finding the maximum sum, longest subarray, and many more. By understanding the basic steps of the algorithm and practicing with examples, we can efficiently solve sliding window problems.

Reference

License

All code in this article is available as open source through the MIT license.

All text and images are free to use under the Creative Commons Attribution 3.0 license. https://creativecommons.org/licenses/by/3.0/us/

These licenses let people distribute, remix, tweak, and build upon the work, even commercially, as long as they give credit for the original creation.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.