  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Sliding Window

Last Updated on March 25, 2022 by Ria Pathak ### CONCEPTS USED:

Sliding Window Technique

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A`, we need to find two sub-arrays with specific lengths `L` and `R` such that sum of these sub-arrays is `Maximum` among all possible choices of sub-arrays and these sub-arrays don’t overlap each other.

See original problem statement here

NOTE:

1. Both sub-arrays should be continuous and should not contain same element.

2. Sub-array L can come after or before sub-array R.

#### For Example:

``````Input : A = [6, 3, 5, 2, 6, 8, 9]
L = 3, R = 2

Output : 32

Explanation: There can be many possible sub-arrays -

[6, 3, 5] [2, 6]
[6, 3, 5] [6, 8]
[6, 3, 5] [8, 9]

[3, 5, 2] [6, 8]
[3, 5, 2] [8, 9]

[5, 2, 6] [6, 3]
[5, 2, 6] [8, 9]

[2, 6, 8] [6, 3]
[2, 6, 8] [3, 5]

[6, 8, 9] [6, 3] --> It gives us maximum value = 32
[6, 8, 9] [3, 5]
[6, 8, 9] [5, 2]``````

### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

1. The simple solution would be to first traverse a sub-array for `L` elements and look for another sub-array with `R` elements from the remaining elements in the array ,take out their `Sum` and compare it with the initial max value.

2. Repeat this process for all such sub-arrays with length `L` and `R` and return the maximum possible value found.

3. `Time Complexity` of this solution will be `O(N^2)`.

EXAMPLE:
Step 1 Step 2 Step 3 Step 4 Step 5 #### EFFICIENT METHOD:

1. The idea is to use `Sliding Window Technique`, where we create a window of `(L+R)` elements initially and keep processing all such windows present in the array.

2. Assume initialize variables `Result` as sum of first window of size `(L+R)`, `lmax` as sum of first `L` elements and `rmax` as sum of first `R` elements.

3. Now move to the next window, we have two cases :

• `L` comes before `R`.
• `R` comes before `L`.
4. When `L` comes before `R`, we will find the sum of starting `L` elements of the current window as `current left` and compare it with our `lmax` value, the higher of the two will be stored in `lmax`, similarly calculate the sum of `R` elements as `current right`, and compare the current `lmax` + `current right` with `Result` and store the maximum of two in the `Result`.

5. When `R` comes before `L`, we will find the sum of starting `R` elements of the current window as `current right` and compare it with our `rmax` value, the higher of the two will be stored in `rmax`, similarly calculate the sum of `L` elements as `current left`, and compare the current `rmax` + `current left` with `Result` and store the maximum of two in the `Result`.

6. Similarly all such windows are processed from `i= (left+right)` to `i<N`.

NOTE: For finding the sum of ranges of array elements quickly, `Prefix Sum Array` can be used, which gives us the sum of any range of elements in an array in `O(1)` `Time Complexity`.

Illustration of Prefix Sum Array:

``````    A[]  = [1, 2, 3, 4, 5]
Prefix[] = [1, 3, 6, 10, 15]

where Prefix[index] gives us the sum of array till i = index.
Prefix = 10
Sum of elements in range [left, right] = Prefix[right] - Prefix[left-1]
sum [2, 4] = Prefix - Prefix[2-1]
= 15 - 3
= 12``````

### SOLUTIONS

```#include <stdio.h>

int max(int a, int b){
return (a>b) ? a:b;
}

int maxSumTwoNoOverlap(int *arr, int n, int l, int r){
/* creating prefix sum array from existing array */
for(int i=1; i<n; i++)
arr[i] += arr[i-1];

//initialize current values
int res = arr[l+r-1];
int lmax = arr[l-1];
int rmax = arr[r-1];

/* Running loop for traversing all the windows and
taking max values of left right and result */
for(int i = l+r; i<n; i++){

lmax = max(lmax, arr[i-r] - arr[i-r-l]);
res = max(res, arr[i] - arr[i-r] + lmax);

rmax = max(rmax, arr[i-l] - arr[i-r-l]);
res = max(res, arr[i] - arr[i-l] + rmax);
}
return res;
}

int main()
{
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);
int l, r; scanf("%d %d", &l , &r);

printf("%d\n", maxSumTwoNoOverlap(arr, n, l, r));
}
return 0;
}```
```#include <bits/stdc++.h>
using namespace std;

int maxSumTwoNoOverlap(int *arr, int n, int l, int r){
/* creating prefix sum array from existing array */
for(int i=1; i<n; i++)
arr[i] += arr[i-1];

//initialize current values
int res = arr[l+r-1];
int lmax = arr[l-1];
int rmax = arr[r-1];

/* Running loop for traversing all the windows and
taking max values of left right and result */
for(int i = l+r; i<n; i++){

lmax = max(lmax, arr[i-r] - arr[i-r-l]);
res = max(res, arr[i] - arr[i-r] + lmax);

rmax = max(rmax, arr[i-l] - arr[i-r-l]);
res = max(res, arr[i] - arr[i-l] + rmax);
}
return res;
}

int main()
{
int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];
for(int i=0; i<n; i++)
cin>>arr[i];
int l, r; cin>>l>>r;

cout<<maxSumTwoNoOverlap(arr, n, l, r)<<"\n";

}

return 0;
}```
```import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
static int maxSumTwoNoOverlap(int []arr, int n, int l, int r){

/* creating prefix sum array from existing array */
for(int i=1; i<n; i++)
arr[i] += arr[i-1];

//initialize current values
int res = arr[l+r-1];
int lmax = arr[l-1];
int rmax = arr[r-1];

/* Running loop for traversing all the windows and
taking max values of left right and result */
for(int i = l+r; i<n; i++){

lmax = Math.max(lmax, arr[i-r] - arr[i-r-l]);
res = Math.max(res, arr[i] - arr[i-r] + lmax);

rmax = Math.max(rmax, arr[i-l] - arr[i-r-l]);
res = Math.max(res, arr[i] - arr[i-l] + rmax);
}
return res;
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();
int l = sc.nextInt();
int r = sc.nextInt();

System.out.println(maxSumTwoNoOverlap(arr, n, l, r));
t--;
}
}
}```

[forminator_quiz id="285"]

This article tried to discuss Sliding Window Technique. Hope this blog helps you understand and solve the problem. To practice more problems on Sliding Window Technique you can check out MYCODE | Competitive Programming.