• Blogs
    • Programming Languages
      • Golang
      • Python
      • Python
      • Javascript
      • C Programming
    • Algorithms & Programming
      • Algorithms
      • Competitive Programming
      • LeetCode Solutions
      • Problems
      • Programming
      • Programming Questions
    • Development & Freelancing
      • Development
      • Freelancing
    • How To
    • Miscellaneous
  • Tutorials
  • Roadmaps

Subscribe to Updates

Get the latest creative news from FooBar about art, design and business.

What's Hot

Matrix Addition in C: A Step-by-Step Guide

August 15, 2023

Rotting Oranges LeetCode Solution

August 14, 2023

Pyttsx3: Text to Speech in Python

August 12, 2023
Facebook X (Twitter) Instagram
CodeWithGeeksCodeWithGeeks
  • Blogs
    • Programming Languages
      • Golang
      • Python
      • Python
      • Javascript
      • C Programming
    • Algorithms & Programming
      • Algorithms
      • Competitive Programming
      • LeetCode Solutions
      • Problems
      • Programming
      • Programming Questions
    • Development & Freelancing
      • Development
      • Freelancing
    • How To
    • Miscellaneous
  • Tutorials
  • Roadmaps
CodeWithGeeksCodeWithGeeks
Home»Competitive Programming»Sliding Window Algorithm in C and C++

Sliding Window Algorithm in C and C++

adminBy adminAugust 10, 20238 Mins Read
Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
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("%dn", maxsum(arr, n, k)); // function call
    printf("%dn", 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("%dn", maxsum(arr, n, k)); // function call
    printf("%dn", 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.

algorithm sliding window
Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
Previous ArticleTop 5 Things Every Coder Should Know 2022
Next Article Swapping Nodes in a Linked List Leetcode Solution 2023
admin
  • Website

Related Posts

LeetCode

Trapping Rain Water LeetCode Solution C, C++, Java & Python

August 10, 2023
LeetCode

Swapping Nodes in a Linked List Leetcode Solution 2023

August 10, 2023
Algorithms

Kadane’s Algorithm: An Efficient Way to Find Maximum Subarray

August 10, 2023
Add A Comment

Leave A Reply Cancel Reply

Top Posts

Roman to Integer Leetcode Solution: A Step-by-Step Guide

August 10, 202315

Blind 75 LeetCode Questions : Top 75 Questions To Crack Coding Interview

August 10, 202312

Difference Between Divide and Conquer and Dynamic Programming

August 10, 20238
Most Popular

Roman to Integer Leetcode Solution: A Step-by-Step Guide

August 10, 202315

Blind 75 LeetCode Questions : Top 75 Questions To Crack Coding Interview

August 10, 202312

Difference Between Divide and Conquer and Dynamic Programming

August 10, 20238
Our Picks

Matrix Addition in C: A Step-by-Step Guide

August 15, 2023

Rotting Oranges LeetCode Solution

August 14, 2023

Pyttsx3: Text to Speech in Python

August 12, 2023

Subscribe to Updates

Get the latest creative news from FooBar about art, design and business.

CodeWithGeeks
  • Home
  • Technology
  • Gaming
  • Phones
  • Buy Now
© 2023 CodeWithGeeks

Type above and press Enter to search. Press Esc to cancel.