Window Sliding Technique In C

Generally, when we use a nested loop like this:

Example


for(i = 1; i <= n; i++)
{
	for(j = i; j < k; j++)
	{
	}
}

Iterations:

The outer loop runs n times, triggering the inner loop to run (k-i) times on each iteration. The overall time complexity for executing the loops averages around O(N^2). As a result, programmers generally advise avoiding the use of loops.

Let's consider an example to gain a clear understanding of the concept:

Suppose we need to determine the highest total of 'k' adjacent elements within an array. The user will input the value of k.

Initially, employing the straightforward method involves iterating through each element i in the array and examining the array from i + 1 to n - 1, with n representing the array's size. This process is repeated for every element to determine the maximum sum by comparing the sums.

Na�ve Brute force method:

Example


#include<stdio.h>
int main()
{
	int n, size, sum=0, max = 0, j;
	printf("Enter the size of the array: ");
	scanf("%d", &n);
	int arr[n], i;
	printf("Enter the elements of the array: ");
	for(i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	printf("Enter the size of sub-array: ");
	scanf("%d", &size);
	for(i = 0; i < (n - size) + 1; i++)
	{
		sum = 0;
		for(j = i; j < i + size; j++)
		{
			sum = sum + arr[j];
		}
		if(sum > max)
		{
			max = sum;
		}
	}
	printf("The maximum sum of %d consecutive elements of the array: %d", size, max);
}

Output:

Output


Enter the size of the array: 7
Enter the elements of the array: 9 2 7 9 4 2 8
Enter the size of the sub-array: 3
The maximum sum of 3 consecutive elements of the array: 20

Now, here comes the sliding window technique:

The idea presented involves establishing a frame of dimension k, which will be continuously shifted by one index. In this context, the frame is not a specialized term. Instead of employing a solitary value as customary in loops, we operate with numerous elements concurrently during each cycle.

For example:

Given an array of size 10:

Suppose the objective is to find the highest sum of 3 consecutive indices in an array. To achieve this, establish a window size of 3 and continuously shift it across the array. Below is a visual illustration:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Iteration 8:

✅ Using this method, there will be no inner loop, and the number of iterations of the one single loop will be (n - k + 1), 8 in this case.
✅ So, a Sliding window is a technique used to reduce the use of nested loops and replace it with a single loop to reduce the total time complexity.
✅ Observe that in every iteration, when the window is sliding to the next index, we're deleting the first element from the previous window and adding a new element that is the next succeeding index.

Here is the code:

Example


#include <stdio.h>
int maxsum(int a[], int k, int n);
int main()
{
	int n, i, k;
	printf("Enter the size of the array: ");
	scanf("%d", &n);
	int arr[n];
	printf("Enter the elements: ");
	for(i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	printf("Enter the value of k: ");
	scanf("%d", &k);
	int max = maxsum(arr, k, n);
	printf("The maximum sum of %d consecutive elements in the array: %d", k,    	max);
}
int maxsum(int a[], int k, int n)
{
	int i, sum, maxm = 0;
	for(i = 0; i < k; i++)
	{
		maxm = maxm + a[i];
	}
	sum = maxm;
	for(i = k; i < n; i++)
	{
		sum += a[i] - a[i - k]; /*subtract the first element of the previous window and add the next index*/
		if(sum > maxm)
		{
			maxm = sum;
		}
	}
	return maxm;
}

Output:

Output


Enter the size of the array: 10
Enter the elements: 8 2 1 7 3 2 5 8 1 3
Enter the value of k: 3
The maximum sum of 3 consecutive elements in the array: 15

✅ The na�ve approach takes O(k*n) time with two nested loops.
✅ The time complexity is reduced to O(n) by using the Sliding window technique.

Here are the steps to apply the technique to any problem at hand:

✅ First, we must see that the window size is constant and shouldn't change. We can use the technique to only such problems.
✅ After you ensure that the window size isn't changing, compute the result of the first window to compare to the computations of the rest of the array.
✅ Now, use a loop to slide the window index by index till the end and keep updating the required value.

Na�ve Brute force method:

Input Required