sliding window technique

Sliding Window Technique

Are you also tired of using two for loop or nested loop, so there is a magic technique known as Sliding window technique which reduces your problem in only one for loop and reduce your program time complexity

Let’s learn it by example

Given a set of array element's
You need to find the maximum sum of 'm' consecutive element's
Suppose 
arr[] ={1,3,2,5,6};
and m = 3;
So, the maximum sum of 3 consecutive elements is 2+5+6 = 13

Let’s try it firstly with brute force technique,

We run our loop starting from index – 0 and run up to index n-m-1 and for every index we check sum of it’s next m elements and if sum is maximum we update our variable,

Here is the code

int maxSumBrute(int arr[],int n,int m)
{
  int currSum = 0,maxSum;
  for(int i = 0;i<n-m-1;i++)
   {
     for(int j = i;j<m+i;j++)
       currSum = currSum+arr[j];
     if(maxSum<currSum)
       maxSum = currSum;
     currSum = 0;
   }
  return maxSum;
}


As you can see above code is nested loop code and time complexity is O(n*m)

Can we solve this in linear Time, Yes Using window sliding technique it is possible. Practice Here

Sliding window technique

Now, Imagine this technique as a Train, where train is array and every window is array element and also there is pane which we slide

Train represent Array

Window represent Element’s

sliding window technique
sliding window technique

See above, Pane is allow to slide and window is fixed, i.e array element.

Pane length is of 3 size and total windows are 5. We start our pane from the 0th index and cover the first 3 elements and calculate sum which is 6

Now, we slide our Pane to next index like this,

Now, Pane length is of again 3 sizes and what we do is, add the next index element covered in the pane and subtract the 0th index(released index). So, sum is 6+5-1=10

10 is maximum element till now, hence we update our variable and now maxSum is 10

We again slide our pane to next window

sliding window technique

Same as above, we add next element covered in pane and subtract released element from left side. Hence sum = 10+6-3 which is 13

13 is greatest element till now and we update our maxSum to 13

Here is the code

int maxSum(int arr[],int n,int m)
{
    
  
    int sum = 0; 
    for (int i=0; i<m; i++) 
       sum += arr[i]; 
   
    int maxSum=sum;
	int in=0;
	for(int i=m;i<n;i++)
	{
		sum=sum+arr[i]-arr[i-m];
		if(sum>maxSum)
		maxSum=sum;
	}
  
    return maxSum; 
}

Practice section – Easy Question, Medium Question on Sliding window

What is sliding window technique

This is a technique used to reduce the time complexity to linear

Where sliding window techniques is used

It is mostly used in competetive programming

Leave a Comment

Your email address will not be published. Required fields are marked *