Sliding Window

Introduction

The Sliding window technique is used to find subarrays in an array that satisfy specific criteria. It is a subset of dynamic programming and forms a basis for many important questions frequently asked in programming interviews.

The technique can be applied to a problem where we have to find the maximum or minimum value for a function that calculates the answer repeatedly for a set of values from the array.

The major advantage of this technique is that it reduces the time required to complete a task(related to a fixed subarray). Problems that would usually take O(N³) or O(N²) time to solve with brute force can be solved in O(N) time using this approach because it avoids repetitive calculations, resulting in improved runtime efficiency.

Let us take an example to be more precise.

Problem Statement:

Consider an array ‘ARR’ of size ‘N.’ Your task is to calculate the maximum sum of ‘K’ consecutive elements in the array.

Example-

ARR[5] = {4, -1, 0, 3, -4}

K = 2

Maximum sum = 3 (Obtained by adding values on index 0 and 1).

2. ARR[7] = { 0, 23, -12, 10, 24, -17, 9 }

K = 3

Maximum sum = 22 (Obtained by adding values on indexes 2,3 and 4).

Let us first analyze the problem with the brute force approach, and then we will discuss the Sliding Window Technique so that we can easily understand the advantage of this approach.

Brute Force Approach

In this approach, we can find the sum of all subarrays of length ‘K’ and return the maximum sum among all the calculated sums.

Starting with the first index, we calculate the sum till the K^thelement and do this for all possible consecutive blocks consisting of K elements using a nested loop.

The outer loop starts with the first index, while the inner loop is used, to sum up till the K^thelement.

Implementation

Program

// C++ program to implement Brute force technique.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum in a subarray of size 'k'.
int maximumSum(vector<int> &arr, int n, int k)
{
    // If the total number of elements is less than 'k,’ it is invalid.
    if (n < k)
    {
        cout << "Invalid values entered.";
        return -1;
    }
 
    // Initializing the variables.
    int maxSum = INT_MIN;
    int curSum;
 
    // Calculating the sum of first 'k' elements in the array using a nested for loop.
    for (int i = 0; i <= n - k; i++)
    {
        curSum = 0;
        for (int j = i; j < i + k; j++)
        {
            curSum += arr[j];
        }
        maxSum = max(maxSum, curSum);
    }
    return maxSum;
}
int main()
{
    vector<int> arr;
    int n, i, a, k;
 
    // Taking user input.
    cout << "Enter the number of elements:\n";
    cin >> n;
    cout << "Enter the value of k\n";
    cin >> k;
    cout << "Enter the elements\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
 
    // Calling the function.
    cout << "The maximum sum of a subarray of size " << k << " is " << maximumSum(arr, n, k);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the value of k:

3

Enter the elements:

0 

23

-12

10

24

-17

9

Output:

The maximum sum of the subarray of size 3 is 22.

Time Complexity

Since this approach uses a nested for loop, the time complexity is given by

O((N -K+1) * K)) or simply O(N*K). The worst-case time complexity is given by O(N²), when K = N/2.

Space Complexity

The space complexity is given by O(1), as we are not using any extra space except variables.

Sliding Window Technique

To understand this concept, we assume the array to be a window of length N and a block of the array as the windowpane of a fixed length K.

The pane slides over the window, performing operations on the sub-arrays and subsequently storing the required result in a variable.

The technique provides an optimal solution, and here are the steps that need to be followed:

The first K elements are added, and their sum is stored in the variable curSum, which denotes the sum of the current elements in the block. This is the first sum and is considered to be maximum initially. So, it is stored in the variable maxSum.
Since the size of the windowpane is K, it slides one place to the right, and the curSum is updated, removing the first element of the previous block and including the last element of the current block.
If the current sum is larger than the maximum, the maxSum is updated, and the above step is repeated till it reaches the last block of the array.

The above-given steps will become more apparent with the help of an example.

Example:

Let us consider an array, ARR, with N = 7, and K = 3. We have to find the maximum sum of a subarray of length K in the array.

ARR[7] = {0, 23, -12, 10, 24, -17, 9}

K = 3

curSum = ARR[0] + ARR[1] + ARR[2]

= 0 + 23 + (-12)

= 11

maxSum = 11

curSum = curSum - ARR[0] +ARR[3]

= ARR[1] + ARR[2] + ARR[3]

= 23 + (-12) + 10

= 21

maxSum = max(21,11) = 21

curSum = curSum - ARR[1] +ARR[4]

= ARR[2] + ARR[3] + ARR[4]

= (-12) + 10 + 24

= 22

maxSum = max(22,21) = 22

curSum = curSum - ARR[2] +ARR[5]

= ARR[3] + ARR[4] + ARR[5]

= 10 + 24 + (-17)

= 17

maxSum = max(22,17) = 22

curSum = curSum - ARR[3] +ARR[6]

= ARR[4] + ARR[5] + ARR[6]

= 24 + (-17) + 9

= 16

maxSum = max(22,16) = 22

Thus, the maximum sum of a subarray of length 3 is equal to 22.

Implementation

Program:

// C++ program to implement Sliding Window Technique.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum in a subarray of size 'k'.
int slidingWindow(vector<int> &arr, int n, int k)
{
    // If the total number of elements is less than 'k', it is invalid.
    if (n < k)
    {
        cout << "Invalid values entered.";
        return -1;
    }
 
    // Initializing the variables as 0.
    int maxSum = 0;
    int curSum = 0;
 
    // Calculating the sum of first 'k' elements in the array.
    for (int i = 0; i < k; i++)
    {
        curSum += arr[i];
    }
 
    // Initially, the maximum sum is equal to the curSum.
    maxSum = curSum;
 
    /*Computing the sum of remaining windows by
     adding the last element of the current window
     and removing the first element of the previous window.*/
    for (int i = k; i < n; i++)
    {
        curSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, curSum);
    }
    return maxSum;
}
int main()
{
    vector<int> arr;
    int n, i, k, a;
 
    // Taking user input.
    cout << "Enter the number of elements:\n";
    cin >> n;
    cout << "Enter the value of k:\n";
    cin >> k;
    cout << "Enter the elements:\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
 
    // Calling the function.
    cout << "The maximum sum of a subarray of size " << k << " is " << slidingWindow(arr, n, k);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the value of k:

3

Enter the elements:

0 

23

-12

10

24

-17

9

Output:

The maximum sum of the subarray of size 3 is 22.

Time Complexity

Since this approach uses a single for loop, which iterates over the array from 1 to N, the time complexity is given by O(N).

Space Complexity

It uses constant space to solve the problem. Thus the space complexity is given by O(1).

Key Takeaways

So, this blog discussed how to solve a problem using the Sliding Window technique in linear time complexity and how it reduces repetitive calculations and improves the runtime efficiency.

To learn more, head over right now to CodeStudio to practice problems on the sliding window technique and crack your interviews like a Ninja!

In case of any comments or suggestions, feel free to post them in the comments section.

By Ishita Chawla