Window Sliding Technique

The window sliding algorithm is used to convert two nested loops (bruth force) into a single loop (linear), which means it enables us to reduce the time complexity from O(n²) to O(n).

 

The following is an example of converting the bruth force approach into the window sliding technique.

 

Given an array A = { 1, 3, 5, 6, 8, 10 }, find the maximum sum of 3 consecutive elements.

 

Bruth Force

int maxSum = 0;

for (int i = 0; i < A.size() - 3; i++)
{
	int sum = 0;
    for (int j = 0; j < 3 + 1; j++)
    {
    	sum += A[i + j];
    }
    maxSum = max(sum, maxSum);
}

return maxSum;

 

Window Sliding

int maxSum = 0;
int panes = 0;
int windowSum = 0;
for (int i = 0; i < sizeA + 1; i++)
{
  if (panes == 3)
  {
    maxSum = max(maxSum, windowSum);
    windowSum -= A[i - 3];
    panes--;
  }

  windowSum += A[i];
  panes++;
}