Sliding Window Technique in C++

Sliding Window Technique or Window Sliding Technique is a computational technique that is mainly used to reduce the use of nested loop and replace it with a single loop. It can also solve problems that involve linear sequences, such as arrays.

Sliding window technique is a subset of dynamic programming where we treat a series of components as a window. It is comparable to a bus window or a sliding door. We remove the last element and add the new part when the window advances. Nested loops are unnecessary because one loop is sufficient to complete our task.

Let’s understand it by an example. Think of a long chain that is connected. Consider applying oil to the entire chain with your hands rather than pouring it from above. Here, one approach is that pick up some oil and rub it onto a portion of the chain. Then rub some more oil onto the next length of the chain where oil has not yet been applied and so on until the entire chain has been lubricated.

Another method is using a towel dipped in oil to hold onto the chain's one end. Instead of repeatedly redipping the material, slide it with your hand onto the next section, the next, and so on until you reach the other end.

The second method is called the Sliding Window Technique, and the Sliding Window refers to the piece that slides from one end to the other.

How to employ the Sliding Window Approach?

When the size of the computation window is fixed for the duration of the entire nested loop, the Sliding Window Approach can be used in a specific situation. The temporal complexity can only be lowered after that.

How to use it?

The following examples show how the sliding window technique is generally used:

• Determine the necessary window size.
• Create the first window's result, starting from the data structure's beginning.
• Next, slide the window by 1 using a loop, and keep calculating the outcome window by window.

Examples

Given an array of integers of size "n," our goal is to get the highest sum of the array's first "k" members.

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

Now, let's use the Brute Force Approach to analyze the issue. Starting with the first index, we add up to the k^th element. We perform it for each set of k items or blocks that can follow one another. This method uses nested for loops; the inner or nested loop will add until the k^th element. The outer for loop starts with the first element of the block of k items.

Example 1:

#include <bits/stdc++.h>
usingnamespace std;
intmaximum(int arr[], int n, int k)
{
    intmax_sum = INT_MIN;
    for (inti = 0; i< n - k + 1; i++) {
        intcurrent_sum = 0;
        for (int j = 0; j < k; j++)
            current_sum = current_sum + arr[i + j];
          max_sum = max(current_sum, max_sum);
    }
  
    returnmax_sum;
}
intmain()
{
    intarr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
    int k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<maxSum(arr, n, k);
    return 0;
}

Output:

24

As can be seen from the code above, which has two nested loops, the time complexity is O(k*n).

Take two pointers, with the first pointer (start) pointing to the array's first element and the second pointer (end) at the k^th position. We will iterate over the first k components using a loop to do this. We will then store the result sum in the example above as needed in a variable. As the window sum, the value kept in the variable will be used.To advance the window, we will first shift the start and end points by one unit, subtract the value at the start pointer from the window sum, and then add the new value of the end pointer to the window sum. We will now receive a new window with a size of k and a further window sum. By simply adding the element at the ith index and removing the piece at the i-k^th index, sliding windows can also be achieved without using two-pointers.

We shall keep doing this till the specified array is finished.

Example 2:

#include <bits/stdc++.h>
usingnamespace std;
int maximum(int arr[], int n, int k)
{
if(n < k)
{
return -1; 
}
int sum = 0;
for(int i = 0; i< k; i++)
sum += arr[i];
int windowsum = sum;
for(int i = k; i< n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = max(sum, windowsum);
}
return sum; 
}
int minsum(int arr[], int n, int k)
{
if(n < k)
{
return -1; 
}
int sum = 0;
for(int i = 0; i< k; i++)
sum += arr[i];
int windowsum = sum;
for(int i = k; i< n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = min(sum, windowsum);
}
return sum;
}
int main()
{
int arr[] = {7, 2, 5, 1, 6, 4, 3}; 
int k = 3; 
int n = sizeof(arr) / sizeof(arr[0]);
cout<<maxsum(arr, n, k)<<endl; 
cout<<minimum(arr, n, k)<<endl; 
return 0;
}

Output:

14
8

Time Complexity

The above method only utilizes one loop; hence its time complexity is O(n).