Sliding Window technique

Introduction:

This technique can be applied in different ways. It can be applied on strings and also on integers. Below are the 2 ways in which we can apply this technique.

1.Fixed size window [this technique we shall study in this chapter]: Here you will be presented with an array and a fixed size window, you need to find the maximum continuous sub array with largest value in that fixed window.

2. Variable size window: Here you will be given an array and a number, you need to find the sub array of any length, to find the continuous elements that adds up that number.

Algorithm Explanation:

As discussed above, you are given an array, and window size. You need to find a continuous sub array with in that window size.

For example:
array = [1, 2, 4, 3, 5, 7, 6]

window size = 2

So by looking at the array we can see that [7, 6] with the window size 2 is having the maximum continuous sub array with largest value in that fixed window.

We can solve the above problem by using brute force method. i.e taking 2 for loops. First loop will start from first index, then in the inner loop will go through all the elements from that index till the window size.

Here the time complexity will be O(n^2). This can be further improved by Sliding Window technique.

By using the sliding window, we can reduce the complexity to O(n).

Below are the steps how we solve using this technique.

Step 1: Calculate the sum of the first k numbers.

Step 2: Move to the next element, then calculate their sum. If the present sum is greater than the previous sum, update the max, else retain the previous value.

Step 3: Continue step 2 till the end of the array is reached.

Understanding Sliding Window technique using an example:

[1, 2, 4, 3, 5, 7, 6]
[1, 2]
[2, 4]
[4, 3]
[3, 5]
[5, 7]
[7, 6] = 13 is the max value.
As you can see from above, we slide the value from element to element. Hence we call it as sliding window approach.

Implementation in C++

#include <iostream> 
using namespace std; 
  
void sliding_window(int arr[], int n, int k) 
{ 
    int max_sum = 0; 
    
    //calculte the value for the first window
    for (int i = 0; i < k; i++) 
        max_sum += arr[i]; 
  
    int current_sum = max_sum; 

    //from the next element, calcute if there is any 
    //sub array that has max value
    for (int i = k; i < n; i++) 
    { 
        current_sum += arr[i] - arr[i - k]; 
        max_sum = max(max_sum, current_sum); 
    } 
    
    cout<<"The max sum using sliding window is "<<max_sum<<endl; 
    return ;
} 
  
int main() 
{ 
    int arr[] = { 1, 2, 4, 3, 5, 7, 6 }; 
    
    int k = 2; 
    
    sliding_window(arr, 7, k); 
    
    return 0; 
}

Output:

The max sum using sliding window is 13