Window Sliding Technique – An Efficient Technique

The window sliding technique if helpful when you have to reduce the time complexity from O(N²) to O(N) by converting nested loop into a single loop in problems that includes linear sequences, like arrays. A window is a contiguous sequence of elements in an array and as the name suggests in the window sliding technique, the window is slid over the array to get desired results.

To make this concept a little more clear, let us take an example. Given an array of integers, and a number k, find the maximum sum of k consecutive elements in the array.

Input: arr[ ] = {1, 8, 30, -5, 20, 7}
k = 3
Output: 45

Input: arr[ ] = {100, 100, 300, 400}
k = 2
Output: 700

Brute Force Approach( Naive Approach)

In this method, we start with the first element of the array and calculate the sum of the first k elements using a for loop and then we store this value in a variable. We repeat this step for the first n-k+1 elements (where n is the size of the given array) using another for loop.

C++ Code implementation in of the above solution is shown below:

#include <bits/stdc++.h>
using namespace std;
 
// this function return the maximum sum of subarray of k-size
int MaximumSum (int arr[], int n, int k){
    int max_sum = INT_MIN, curr_sum, i,j;
//here max_sum has been assigned minimum value since we have also considered negative value of integer
    for(i=0;i<n-k+1;i++){
        curr_sum = 0; //in every iteration we are updating the value of curr_sum to 0
        for(j=0;j<k;j++){
            curr_sum = curr_sum + arr[i+j]; //calculating the sum of k consecutive elements in an array
        }
        max_sum = max(max_sum, curr_sum);// updating the max_sum with the current maximum value 
    }
    return max_sum;
}
 
// Main function
int main()
{
    int arr[] = {5, -10, 6, 90, 3};
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << MaximumSum(arr, n, k);
    return 0;
}

Output: 96

Here you can observe that the time complexity is O(n*k) as the above program contains a nested loop. In order to make this solution more efficient and make its time complexity to O(N), we use the window sliding technique.

Window Sliding Technique

Steps to apply sliding window technique are as follows:

In this approach, we take the sum of the first k elements of the given array and we store it in a variable. Then we’ll slide over the entire array while keeping track of the maximum sum. For sliding, we eliminate the first element and add the element next to the last element of the window.

Implementation of sliding window technique in C++ is shown below:

#include <bits/stdc++.h>
using namespace std;
 
// this function return the maximum sum of subarray of k-size
int MaximumSum (int arr[], int n, int k){
    int max_sum, curr_sum=0, i;
//here max_sum has been assigned minimum value since we have also considered negative value of integer
    for(i=0;i<k;i++){
        curr_sum += arr[i]; 
    }
    max_sum = curr_sum;
    for(i=k;i<n;i++){
        curr_sum += arr[i]-arr[i-k]; //window sliding technique
        max_sum = max(max_sum, curr_sum);
    }
    
    return max_sum;
}
 
// Main function
int main()
{
    int arr[] = {5, -10, 6, 90, 3};
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << MaximumSum(arr, n, k);
    return 0;
}

Output: 96

Let’s perform a dry run:

arr[ ] = {5, -10, 6, 90, 3};
k = 2;
n = 5

After the implementation of first for loop we get max_sum = curr_sum = -5
Coming to the next for loop we have i = 2, therefore we have curr_sum = -5+6-5 = -4 and max_sum = -4
In next iteration, i = 3, curr_sum = -4+90-(-10) = 96, max_sum = 96
In next iteration, i = 4, curr_sum = 96+3-6 = 93, max_sum = 96
Therefore, the output = 96

As you can see that in window sliding technique since only one loop is running at a time, the time complexity is O(N). Hope you enjoyed the article. You can also checkout another article: Sieve of Eratosthenes