### Sliding Window Algorithm - The Coding Shala

Last Updated: 27-Jan-2021
Home >> Algorithms >> Sliding Window Algorithm

In this post, we will learn what is Sliding Window Algorithm and how to implement it in Java.

## Sliding Window Algorithm

What do you mean by Sliding Window? A window of fixed length can be slide over the input. The sliding window algorithm is used to reduce the time complexity by converting the nested for loops into a single for loop.

Let's take an example and understand the sliding window problem. we have given an array of integers of size n and need to find the maximum sum of k consecutive elements in the array.

Input array:  { 100, 200, 300, 400}
k = 2
Output: 700

So how we solve this problem we start outer loop from index 0 and inner loop runs till i+k size every time and compare the maximum sum.

The following is the code for this brute force approach.

Java Program:

```static int maxSum(int arr[], int n, int k)
{
// Initialize result
int max_sum = Integer.MIN_VALUE;

// Consider all blocks starting with i.
for (int i = 0; i < n - k + 1; i++) {
int current_sum = 0;
for (int j = 0; j < k; j++)
current_sum = current_sum + arr[i + j];

// Update result if required.
max_sum = Math.max(current_sum, max_sum);
}

return max_sum;
}
```

Now how do we solve this problem using a sliding window? We will take a window of size k and then move that window to find the maximum sum.

Array:  {100, 200, 300, 400}         window size:  2
----------
300
---------
500
----------
700
max output it 700.

So using Sliding Window Algorithm we can solve this problem using a single loop.

Java Program:
```//sliding window algorithm
//thecodingshala.com

class Main{

public static int sliding_window(int[] input, int k) {
int len = input.length;
int max_sum = 0;
//compute first window
for(int i=0; i<k; i++) {
max_sum += input[i];
}

int window_sum = max_sum;
//compute window sum every time and check with max_sum
for(int i=k; i<len; i++) {
window_sum += input[i]-input[i-k];
max_sum = Math.max(max_sum, window_sum);
}

return max_sum;
}

public static void main(String[] args) {
int[] input = {100, 200, 300, 400};
int k = 2;
System.out.println("Max sum is: "+ sliding_window(input, k));
}
}
```

Other Posts You May Like