## Introduction

Sliding window technique is use for reducing some redundant calculation which slow down program. like it can reduce time complexity from O(n^2) to O(n) with O(1) space complexity.

## Why use it?

First of all it reduce time coplexity and also with O(1) space complexity. so let’s understand with Example…

So we want to find maximum sum of k consecutive integer from array, so brute force would look like this for k=5,

```
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
int final_max = 0;
for(int i=0;i<arr.size()-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;
}
```

But time complexity of above program is O(nk)

**Brute Force Approach**

As per we can see in above image brute approach checks every patter of k length(here k=5). if you compare above code with this image you will understand it.

here k=5 so it won’t make too much different in O(n) and O(nk) but what if k is too big. then it will impact running time of program, so what to do now? can we implement this above code to O(n)?

Answer is YES!! , with use of sliding window we can reduce time complexity of above code O(n).

## How Sliding Window Works?

So let’s see how sliding window works.

let me give you simple visual with small array,

```
{5,2,6,7,7,3,2,1,3,9}
for k=3 (because k=5 is too much to write)
{5,2,6} --> first 3 elements
{2,6,7} --> remove 5 and add 7
{6,7,7} --> remove 2 and add 7
{7,7,3} --> remove 6 and add 3
{7,3,2} --> remove 7 and add 2
{3,2,1} --> remove 7 and add 1
{2,1,3} --> remove 3 and add 3
{1,3,9} --> remove 2 and add 9
```

let’s understand with second example,

```
{5, 7, 1, 4, 3, 6, 2, 9, 2}
k=5
{5,7,1,4,3} --> first 5
{7,1,4,3,6} --> remove 5 and add 6
and so on.
```

As we can see in above image it move one step at one time. so this is how actually it works.

## Let’s Code

Code for maximum sum of k consecutive integer from array, using sliding window technique.

```
#include<iostream>
#include<vector>
using namespace std;
int sum_of_k_ele(vector<int> arr,int k){
int sum = 0;
for(int i=0;i<k;i++){
sum += arr[i];
}
return sum;
}
int main(){
vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
int k=3;
// below function will be used only once
// for finding sum of first k digits
int final_sum = sum_of_k_ele(arr,k);
int temp_sum = final_sum;
for (int i=k;i<arr.size();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;
}
```

## When to use?

- When you are looking for subrange in given string or array like highest or smallest value or targeted value.
- it involves data structure which is iterable like string or array.
- when there can be brute force solution with O(n^2) or (2^n)

## More Examples…

- Find all anagrams in a string --> Solution
- Permutation in string --> Solution

**Note :**Solutions in above questions are just plain code.

## References

Thank You ðŸ˜ŠðŸ˜Š

## 0 Comments:

## Post a Comment