Hello geeks 😁, In this article we are going to learn about the sliding window algorithm using C and C++.
Introduction
Sliding window is a subset of dynamic programming which is used in conditions where we are required to find subarray or substring which satisfy the given conditions. It is mostly used to give a better solution than nested loop.
Problem
To begin with, let’s consider a problem in which we are given an array and we are required to find maximum and minimum sum of subarray of given size.
Let the given array arr= [7, 2, 5, 1, 6, 4, 3] and let the size of the the required subarray be k=3
We are required to find the maximum sum and minimum sum of the subarray of the given size.
It can be solved easily using the brute force approach. We will take nested loops and find the sum of consecutive k elements from the starting index. We will repeat this for all the elements and will find the max and min sum from it.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Function to calculate max sum of subarray
int maxsum(int arr[], int n, int k)
{
int maximum_sum = INT_MIN;
for (int i = 0; i <= n - k; i++) // simple brute force approach
{
int sum = 0;
for (int j = i; j < k + i; j++)
{
sum += arr[j];
}
maximum_sum = max(maximum_sum, sum);
}
return maximum_sum;
}
// Function to calculate min sum of subarray
int minsum(int arr[], int n, int k)
{
int minimum_sum = INT_MAX;
for (int i = 0; i <= n - k; i++) // simple brute force approach
{
int sum = 0;
for (int j = i; j < k + i; j++)
{
sum += arr[j];
}
minimum_sum = min(minimum_sum, sum);
}
return minimum_sum;
}
int main()
{
int arr[] = {7, 2, 5, 1, 6, 4, 3}; // array
int k = 3; // given size of subarray
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxsum(arr, n, k) << "\n"; // function call
cout << minsum(arr, n, k) << "\n"; // function call
return 0;
}
Implementation in C
#include <stdio.h>
#include <limits.h>
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a > b)
return b;
return a;
}
// Function to calculate max sum of subarray
int maxsum(int arr[], int n, int k)
{
int maximum_sum = INT_MIN;
for (int i = 0; i <= n - k; i++) // simple brute force approach
{
int sum = 0;
for (int j = i; j < k + i; j++)
{
sum += arr[j];
}
maximum_sum = max(maximum_sum, sum);
}
return maximum_sum;
}
// Function to calculate min sum of subarray
int minsum(int arr[], int n, int k)
{
int minimum_sum = INT_MAX;
for (int i = 0; i <= n - k; i++) // simple brute force approach
{
int sum = 0;
for (int j = i; j < k + i; j++)
{
sum += arr[j];
}
minimum_sum = min(minimum_sum, sum);
}
return minimum_sum;
}
int main()
{
int arr[] = {7, 2, 5, 1, 6, 4, 3}; // array
int k = 3; // given size of subarray
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxsum(arr, n, k)); // function call
printf("%d\n", minsum(arr, n, k)); // function call
return 0;
}
Time Complexity: The time complexity of the above algorithm is O(n*k).
This is not an optimal solution as here we have a lot of redundancy as the same element is repeatedly included in sums.
What is Sliding window?
Sliding window technique is a subset of dynamic programming in which we take consecutive elements and consider them as a window. It is analogous to a sliding door or a window in a bus. As the window moves forward we subtract the previous element and add the new element. Here we don’t require nested loops as our work can be done with help of one loop.
The basic idea behind this is to take two pointers, first pointer(start) will be pointing to first element of array and the second pointer(end) will be at kth position. To implement this we will be using a loop and iterate over first k elements and store there result(Sum in the above example) as required in a variable. The value stored in variable will be treated as the window sum.
Now to move window forward we will subtract the value at start pointer from the window sum, move both start and end by one unit and then add the new value of the end pointer to the window sum. Now we will get our new window of size k and a new window sum. Sliding window can also be implemented without using two pointers by just adding the element at ith and subtracting the element at i-kth index.
This process will be repeated until we reach the end of given array.
Implementation of above discussed problem using sliding window technique:-
C++ code
#include <bits/stdc++.h>
using namespace std;
int maxsum(int arr[], int n, int k)
{
if (n < k)
{
return -1; // Window size cannot be greater than size of array
}
int sum = 0;
for (int i = 0; i < k; i++)
sum += arr[i];
int windowsum = sum;
for (int i = k; i < n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = max(sum, windowsum);
}
return sum;
}
int minsum(int arr[], int n, int k)
{
if (n < k)
{
return -1; // Window size cannot be greater than size of array
}
int sum = 0;
for (int i = 0; i < k; i++)
sum += arr[i];
int windowsum = sum;
for (int i = k; i < n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = min(sum, windowsum);
}
return sum;
}
int main()
{
int arr[] = {7, 2, 5, 1, 6, 4, 3}; // array of integers
int k = 3; // given window size
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxsum(arr, n, k) << endl; // function call
cout << minsum(arr, n, k) << endl; // function call
return 0;
}
C code
#include <stdio.h>
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a > b)
return b;
return a;
}
int maxsum(int arr[], int n, int k)
{
if (n < k)
{
return -1; // Window size cannot be greater than size of array
}
int sum = 0;
for (int i = 0; i < k; i++)
sum += arr[i];
int windowsum = sum;
for (int i = k; i < n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = max(sum, windowsum);
}
return sum;
}
int minsum(int arr[], int n, int k)
{
if (n < k)
{
return -1; // Window size cannot be greater than size of array
}
int sum = 0;
for (int i = 0; i < k; i++)
sum += arr[i];
int windowsum = sum;
for (int i = k; i < n; i++)
{
windowsum += arr[i] - arr[i - k];
sum = min(sum, windowsum);
}
return sum;
}
int main()
{
int arr[] = {7, 2, 5, 1, 6, 4, 3}; // array of integers
int k = 3; // given window size
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxsum(arr, n, k)); // function call
printf("%d\n", minsum(arr, n, k)); // function call
return 0;
}
Time complexity: Time complexity of the above approach is O(n) as it only uses one loop.
You can try out the codes in our very own IDE https://ide.codewithgeeks.com/.
Sliding window is very easy to implement and act as one of the best substitutions to nested loops in order to get an optimal solution. In many cases we have to compare the content or related data of the current window to all other windows. This method can be implemented in many questions. To know where to implement requires practice.
FAQ
1) What is the sliding window algorithm?
Ans) Sliding window algorithm is a technique in which we mostly try to reduce the time complexity of a problem to O(n) by taking a group of consecutive elements as window and performing operations on it as we move forward.
2) Is sliding window algorithm a Dynamic Programming?
Ans) Sliding window algorithm is a subset of dynamic programming but the approach is a bit different from storing the results of expensive function calls.
Conclusion
In this article we learnt about Sliding window algorithm and how it can be applied to reduce the time complexity of a problem. Sliding window in many cases gives the optimal solution and can be applied to many questions. Implementing it to questions comes in hand with more practice.