Sliding Window Technique – DEV Community



Introduction

The sliding window approach is used for lowering some redundant calculations that decelerate this system. like it might scale back time complexity from O(n^2) to O(n) with O(1) house complexity.



Why use it?

To start with it scale back time coplexity and likewise with O(1) house complexity. so let’s perceive with Instance..
So we need to discover most sum of okay consecutive integer from array, so brute power would seem like this for okay=5,

#embrace<iostream>
#embrace<vector>
utilizing namespace std;
int major(){
    vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
    int final_max = 0;
    for(int i=0;i<arr.measurement()-5;i++){
        int temp_max = 0;
        for(int j=i;j<i+5;j++){
            temp_max += arr[j];
        }
        if(temp_max>final_max){
            final_max = temp_max;
        }
    }
    cout << final_max << endl;
    return 0;
}
Enter fullscreen mode

Exit fullscreen mode

However time complexity of the above program is O(nk)

Brute Power Strategy


As per we will see within the above picture brute strategy checks each sample of okay size(right here okay=5). when you evaluate the above code with this picture you’ll perceive it.

right here okay=5 so it will not make an excessive amount of distinction in O(n) and O(nk) however what if okay is just too large. then it’ll affect the working time of this system, so what to do now? can we implement the above code to O(n)?

The reply is YES!! , with the usage of the sliding window, we will scale back the time complexity of the above code O(n).



How does Sliding Window Works?

So let’s have a look at how sliding window works.
let me provide you with easy visible with small array,

{5,2,6,7,7,3,2,1,3,9}
for okay=3 (as a result of okay=5 is an excessive amount of to write down)
{5,2,6} --> first 3 components
{2,6,7} --> take away 5 and add 7 
{6,7,7} --> take away 2 and add 7
{7,7,3} --> take away 6 and add 3
{7,3,2} --> take away 7 and add 2
{3,2,1} --> take away 7 and add 1
{2,1,3} --> take away 3 and add 3
{1,3,9} --> take away 2 and add 9
Enter fullscreen mode

Exit fullscreen mode

let’s perceive with second instance,

 {5, 7, 1, 4, 3, 6, 2, 9, 2}
 okay=5
 {5,7,1,4,3} --> first 5
 {7,1,4,3,6} --> take away 5 and add 6
 and so forth.
Enter fullscreen mode

Exit fullscreen mode

Image description
As we will see within the above picture it strikes one step at one time. so that is how truly it really works.



Let’s Code

Code for a most sum of okay consecutive integer from the array, utilizing the sliding window approach.

#embrace<iostream>
#embrace<vector>
utilizing namespace std;
int sum_of_k_ele(vector<int> arr,int okay){
    int sum = 0;
    for(int i=0;i<okay;i++){
        sum += arr[i];
    }
    return sum;
}
int major(){
    vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
    int okay=3;
    // under operate might be used solely as soon as 
    // for locating sum of first okay digits
    int final_sum = sum_of_k_ele(arr,okay);

    int temp_sum = final_sum;
    for (int i=okay;i<arr.measurement();i++){
        temp_sum = temp_sum - arr[i-k];
        temp_sum = temp_sum + arr[i];
        if(temp_sum>final_sum){
            final_sum = temp_sum;
        } 
    }
    cout << final_sum << endl;

    return 0;
}
Enter fullscreen mode

Exit fullscreen mode



When to make use of?

  • If you find yourself on the lookout for a subrange in a given string or array-like highest or smallest worth or focused worth.

  • it includes information construction which is iterable like string or array.

  • when there will be brute power resolution with O(n^2) or (2^n)



Extra Examples…

Observe : Options in above questions are simply plain code.

## References

Thank You 😊😊

Add a Comment

Your email address will not be published. Required fields are marked *