### Introduction

The Sliding window technique is used to find subarrays in an array that satisfy specific criteria. It is a subset of __dynamic programming__* *and forms a basis for many important questions frequently asked in programming interviews.

The technique can be applied to a problem where we have to find the maximum or minimum value for a function that calculates the answer repeatedly for a set of values from the array.

The major advantage of this technique is that it reduces the time required to complete a task(related to a fixed subarray). Problems that would usually take * O(N^{3})* or

*time*

**O(N**^{2})*to solve with brute force*

*can be solved in*

*time using this approach because it avoids repetitive calculations, resulting in improved runtime efficiency.*

**O(N)**Let us take an example to be more precise.

__Problem Statement:__

__Problem Statement:__Consider an array * ‘ARR’ *of size

*Your task is to calculate the*

**‘N.’***maximum*sum of

*consecutive elements in the array.*

**‘K’**__Example-__

__Example-__

[**ARR**] = {**5**}**4, -1, 0, 3, -4**

* K *=

**2**

Maximum sum =* 3 *(Obtained by adding values on index

*and*

**0***).*

**1**2. * ARR*[

*] = {*

**7***}*

**0, 23, -12, 10, 24, -17, 9*** K *=

**3**Maximum sum =* 22 *(Obtained by adding values on indexes

*and*

**2,3***).*

**4**Let us first analyze the problem with the *brute force approach*, and then we will discuss the Sliding Window Technique so that we can easily understand the advantage of this approach.

**Brute Force Approach**

In this approach, we can find the sum of all subarrays of length ‘* K*’ and return the maximum sum among all the calculated sums.

Starting with the first index, we calculate the sum till the * K^{th }*element and do this for all possible consecutive blocks consisting of

*elements using a nested loop.*

**K**The outer loop starts with the first index, while the inner loop is used, to sum up till the * K^{th }*element.

**Implementation**

**Implementation**

__Program__

```
// C++ program to implement Brute force technique.
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum in a subarray of size 'k'.
int maximumSum(vector<int> &arr, int n, int k)
{
// If the total number of elements is less than 'k,’ it is invalid.
if (n < k)
{
cout << "Invalid values entered.";
return -1;
}
// Initializing the variables.
int maxSum = INT_MIN;
int curSum;
// Calculating the sum of first 'k' elements in the array using a nested for loop.
for (int i = 0; i <= n - k; i++)
{
curSum = 0;
for (int j = i; j < i + k; j++)
{
curSum += arr[j];
}
maxSum = max(maxSum, curSum);
}
return maxSum;
}
int main()
{
vector<int> arr;
int n, i, a, k;
// Taking user input.
cout << "Enter the number of elements:\n";
cin >> n;
cout << "Enter the value of k\n";
cin >> k;
cout << "Enter the elements\n";
for (i = 0; i < n; i++)
{
cin >> a;
arr.push_back(a);
}
// Calling the function.
cout << "The maximum sum of a subarray of size " << k << " is " << maximumSum(arr, n, k);
return 0;
}
```

__Input:__

```
Enter the number of elements:
7
Enter the value of k:
3
Enter the elements:
0
23
-12
10
24
-17
9
```

__Output:__

`The maximum sum of the subarray of size 3 is 22. `

**Time Complexity**

**Time Complexity**

Since this approach uses a nested *for *loop, the time complexity is given by

* O((N -K+1) * K))* or simply

*The worst-case time complexity is given by*

**O(N*K).***when*

**O(N**^{2}),

**K = N/2.****Space Complexity**

**Space Complexity**

The space complexity is given by * O(1), *as we are not using any extra space except variables.

**Recommended topic, **__kth largest element in an array__** **and

__Euclid GCD Algorithm__**Sliding Window Technique**

To understand this concept, we assume the array to be a window of length* N *and a block of the array as the windowpane of a fixed length

*.*

**K**The pane slides over the window, performing operations on the sub-arrays and subsequently storing the required result in a variable.

The technique provides an optimal solution, and here are the steps that need to be followed:

- The first
elements are added, and their sum is stored in the variable**K**which denotes the sum of the current elements in the block. This is the first sum and is considered to be maximum initially. So, it is stored in the variable*maxSum.* - Since the size of the windowpane is
it slides one place to the right, and the**K,***curSum*is updated, removing the first element of the previous block and including the last element of the current block. - If the current sum is larger than the maximum, the
*maxSum*is updated, and the above step is repeated till it reaches the last block of the array.

The above-given steps will become more apparent with the help of an example.

#### Example:

Let us consider an array, * ARR, *with N =

*and K =*

**7,***We have to find the maximum sum of a subarray of length K in the array.*

**3.**** ARR[****7****] **= {* 0, 23, -12, 10, 24, -17, 9*}

* K *=

**3**1)

** curSum*** *=

**ARR**[

**0**] +

**ARR**[

**1**] +

**ARR**[

**2**]

= 0 + 23 + (-12)

= 11

** maxSum** = 11

2)

** curSum = curSum** - **ARR[0] **+**ARR**[**3**]

** ** = **ARR**[**1**] + **ARR**[**2**] + **ARR**[**3**]

** ** = 23 + (-12) + 10

** ** = 21

** maxSum** = max(21,11) = 21

3)

** ** **curSum = curSum **- **ARR[1] **+**ARR**[**4**]

** **=** ARR**[**2**] + **ARR**[**3**] + **ARR**[**4**]

** ** = (-12) + 10 + 24

** ** = 22

** maxSum** = max(22,21) = 22

4)

** curSum = curSum** - **ARR[2] **+**ARR**[**5**]

** **= **ARR**[**3**] + **ARR**[**4**] + **ARR**[**5**]

** ** = 10 + 24 + (-17)

** ** = 17

** maxSum **= max(22,17) = 22

5)

** curSum = curSum **- **ARR[3] **+**ARR**[**6**]

** **= **ARR**[**4**] + **ARR**[**5**] +** ARR**[**6**]

** ** = 24 + (-17) + 9

** ** = 16

** maxSum **= max(22,16) = 22

Thus, the maximum sum of a subarray of length* 3* is equal to

**22.****Implementation**

**Implementation**

__Program:__

```
// C++ program to implement Sliding Window Technique.
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum in a subarray of size 'k'.
int slidingWindow(vector<int> &arr, int n, int k)
{
// If the total number of elements is less than 'k', it is invalid.
if (n < k)
{
cout << "Invalid values entered.";
return -1;
}
// Initializing the variables as 0.
int maxSum = 0;
int curSum = 0;
// Calculating the sum of first 'k' elements in the array.
for (int i = 0; i < k; i++)
{
curSum += arr[i];
}
// Initially, the maximum sum is equal to the curSum.
maxSum = curSum;
/*Computing the sum of remaining windows by
adding the last element of the current window
and removing the first element of the previous window.*/
for (int i = k; i < n; i++)
{
curSum += arr[i] - arr[i - k];
maxSum = max(maxSum, curSum);
}
return maxSum;
}
int main()
{
vector<int> arr;
int n, i, k, a;
// Taking user input.
cout << "Enter the number of elements:\n";
cin >> n;
cout << "Enter the value of k:\n";
cin >> k;
cout << "Enter the elements:\n";
for (i = 0; i < n; i++)
{
cin >> a;
arr.push_back(a);
}
// Calling the function.
cout << "The maximum sum of a subarray of size " << k << " is " << slidingWindow(arr, n, k);
return 0;
}
```

__Input:__

```
Enter the number of elements:
7
Enter the value of k:
3
Enter the elements:
0
23
-12
10
24
-17
9
```

__Output:__

`The maximum sum of the subarray of size 3 is 22. `

**Time Complexity**

**Time Complexity**

Since this approach uses a single *for *loop, which iterates over the array from 1 to N, the time complexity is given by **O(N).**

**Space Complexity**

**Space Complexity**

It uses constant space to solve the problem. Thus the space complexity is given by **O(1).**

## Key Takeaways

So, this blog discussed how to solve a problem using the Sliding Window technique in linear time complexity and how it reduces repetitive calculations and improves the runtime efficiency.

To learn more, head over right now to* ** Coding Ninjas Studio* to practice problems on the sliding window technique and crack your interviews like a Ninja! You can also consider our

__System Design Course__to give your career an edge over others.

In case of any comments or suggestions, feel free to post them in the comments section.

**By Ishita Chawla**