Competitive Programming, Problems, Programming Questions

Sliding Window Algorithm in C and C++

7 min read
Sliding Window Algorithm

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.


Leave a Reply

Your email address will not be published.

Sign up for our Newsletter

Get all the latest updates on what’s happening in the tech & startup world, delivered straight to your inbox from us.