# Window Sliding Technique

Sliding window technique is useful for solving problems in array or string, especially it is considered as a technique that could reduce the time complexity from O(n²) to O(n).

where can we apply this:

```
calculate the maximum sum of 'k'
consecutive elements in the array.
Input : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
k = 4
Output : 39
We get maximum sum by adding subarray {4, 2, 10, 23}
of size 4.
Input : arr[] = {7,8}
k = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.
```

The **Naive Approach **to solve this problem is to calculate sum for each of the blocks of K consecutive elements and compare which block has the maximum sum possible. The time complexity of this approach will be O(n * k).

** Window Sliding Technique**

Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. We do this via maintaining a subset of items as our window, and resize and move that window within the larger list until we find a solution.The above problem can be solved in Linear Time Complexity by using Window Sliding Technique by avoiding the overhead of calculating sum repeatedly for each block of k elements.

Consider an array **arr[] **= {5 , 2 , -1 , 0 , 3} and value of **k = **3 and** n =** 5

**Applying sliding window technique :**

1)We compute the sum of first k elements out of n terms using a linear loop and store the sum in variable window_sum.

2)Then we will graze linearly over the array till it reaches the end and simultaneously keep track of maximum sum.

3)To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block .

The below representation will make it clear how the window slides over the array.

we first calculated the initial window sum starting from index 0 . At this stage the window sum is 6. Now, we set the maximum_sum as current_window i.e 6.

{5,2,-1,0,3} //current window in red = 5+2-1=6

current_sum=window_sum

Now, we slide our window by a unit index. so 5 is removed and 0 is added So, our window sum now becomes 1. Now, we will compare this window sum with the maximum_sum. As it is smaller we wont the change the maximum_sum.

{5,2,-1,0,3} //current window in red = 2-1+0=1

current_sum=window_sum-5+0

Similarly, now once again we slide our window by a unit index and obtain the new window sum to be 2. Again we check if this current window sum is greater than the maximum_sum till now. Once, again it is smaller so we don't change the maximum_sum.

Therefore, for the above array our maximum_sum is 6.

{5,2,-1,0,3} //current window in red = -1+0+3=2

current_sum=window_sum-2+3