Logicmojo - Updated Jan 2, 2024
Introduction
If you learn computer science, you will undoubtedly come across a variety of algorithms. The sliding window algorithm is one such algorithm that is used in areas such as computer networks and data communication. It is used for flow management in the TCP (Transmission Control Protocol). Aside from that, several competitive problems can be formed using this algorithm; thus, you must grasp this algorithm in order to ace your dream company's interview. We explore the sliding window algorithm in this article.
The Sliding Window Algorithm is a method for reducing algorithm complexity. It is used in such a way that the need for reusing loops is reduced, and thus the software is optimised. In this technique, we use the prior step's result to compute the next step's result.
What is Sliding Window Algorithm?
It is an algorithm that allows us to quickly compute things that have a fixed calculation window and retrieve the results in a more efficient way than nested loops (naive approach). This algorithm's primary goal is to reuse the result of one window to compute the result of the next window.
The problem requires that the sliding window method be used to find the maximum (or minimum) value for a function that calculates the answer repeatedly for a set of ranges from the array. Specifically, if these ranges can be sorted based on their beginning and ending points, we can use the sliding window technique.
The sliding window method works by combining two nested loops into a single loop.
The following are some basic clues to identifying this type of problem:
The issue will be based on a data structure such as an array, list, or string.
It will request that you identify a subrange in that array or string and provide the longest, shortest, or target values.
Its concept is primarily based on ideas such as the longest or shortest sequence of something that completely meets a given condition.
Let's assume you have an array like this:
The above Image shows how the sliding window technique works.
How to use Sliding Window Technique in Problem Statement?
ILet us first comprehend the problem before proceeding with its solution. The issue statement is as follows: given an array of size N, determine the largest sum of K consecutive entries. Not positive if you understand? Don't worry, we'll explain it with an illustration.
Assume we are provided the following array and asked to identify three consecutive numbers in it that add up to the greatest sum. In this instance, k is equal to 3.
array = [20, 10, 30, 40, 20, 10]
The following are blocks having three consecutive entries from the given array:[20, 10, 30] , [10, 30, 40] , [30, 40, 20] , [40, 20, 10].
The sum of first three are 20+10+30 = 60, and the second are 10+30+40 = 80, so on till last. Here, we can compare the sums calculated at each step to find the required answer.
Ways to Solve Sliding Window Problems
The following are the stages for using the Sliding Window technique:
Determine the extent of the window in which the algorithm must be run.
Calculate the result of the first window in the same way that we did in the naive method.
Keep a pointer on the starting location.
Then, in a loop, slide the window one step at a time while also sliding the pointer one step at a time, keeping note of the results for each window.
Naive approach
There is an unbalanced but simple answer to this problem. You may be thinking why we are discussing this strategy when it is ineffective. Well, one must understand the significance of a solid approach, right? Understanding this approach also enables us to build on our knowledge to create a more efficient algorithm known as the sliding window algorithm.
In this technique, we start with the first index and work our way up until we hit the kth element. We repeat the procedure for all possible consecutive blocks or groups of k elements. This approach uses a stacked for loop, with the outer for loop starting with the first element of the k-element block and continuing until the kth element is reached.
The complexity of this approach is O(N*K) because it includes two nested loops. Where n denotes the size of the array and k denotes the number of consecutive subentries to be evaluated. Can you believe it when we tell you that this job can be completed in much less time? Check it out for yourself below.
#include<bits/stdc++.h> using namespace std; int findMaxSum(int array[], int x, int y) { int max_result = INT_MIN; for (int i = 0; i <= x - y ; i++) { int current_sum = 0; for (int j = i; j < i+y && j < x; j++) current_sum = current_sum + array[j]; // Update the max_result variable. max_result = max(current_sum, max_result); } return max_result; } int main() { int x = 6; int array[x] = { 20, 10, 30, 40, 20, 10}; int y = 3; int ans = findMaxSum(array, x, y); cout<<ans; return 0; }
Output
90
Sliding Window Technique
Let us use an example to better comprehend this approach. Consider a window with length n and a fixed partition with length k. That pane was initially located at the far left, or 0 units from the left. Relationship the window to the n-element collection arr[] and the pane to the k-element current sum. If we apply power to the window, it will move one unit forward. The pane will contain the following k components.
At each step, the current sum is determined by adding the last element of the current block and subtracting the first element of the prior block. That's all! This describes the entire sliding window method.
Algorithm for Sliding Window
Using the Sliding window technique:
Using a linear loop, we calculate the sum of the first k elements from n terms and store the result in the variable maximum_sum.
Then we'll graze the array linearly until it reaches the end while keeping track of the highest sum.
Simply subtract the first element from the prior block and add the last element of the current block to get the current_sum of a k-element block.
Example
Let us now look at an example to better grasp the algorithm. Before we begin the procedure, the maximum_sum variable is set to 0.
arr[] = [20, 10, 30, 40, 20, 10] , k = 3 , x = 3
We start by calculating the sum of the first three consecutive integers, i.e. from index 0 to 2. The sum of this first window is 60, which is stored in the current_Sum variable. Because current_Sum is higher than maximum_Sum, the value of the maximum_Sum variable is updated to 60.
To encompass the next three consecutive numbers, the window is slid by a unit distance. The new current window's total is calculated by subtracting 20 from the current_Sum and adding 40. The currentSum has now reached 80. The most recent currentSum value is now compared to the maximum_sum value, and because it is larger, the maximum_sum variable is set to 80.
The window is shifted once more to encompass the next three consecutive numbers. To calculate the total of this window, subtract 10 from the current_sum and add 20, getting 90. Because this value is more than maximum_sum, the value of maximum_sum will change to 90.
The window has now been shifted to encompass the last three consecutive numbers. At this point, the total is determined to be 70. Because this value is less than maximum_sum (90), its value stays unchanged. All possible three-number combinations have now been found, and their sums have been calculated. Finally, the maximum_sum, identified as 90, is given.
C++ Code Implementation for Sliding Window Algorithm
#include <bits/stdc++.h> using namespace std; int maximum_sum(int arr[], int x, int y) { // calculate the sum of first m elements of that array // and store that sum in a variable named running_sum. int max_result = 0; for (int i = 0; i < y; i++) max_result += arr[i]; // Calculate sum of the remaining windows by // summing up the next element subtracting the // previous element. int current_sum = max_result; for (int i = y; i < x; i++) { current_sum = current_sum + (arr[i] - arr[i - y]); max_result = max(max_result, current_sum); } return max_result; } int main() { int x = 6; int arr[x] = { 20, 10, 30, 40, 20, 10 }; int y = 3; int ans = maximum_sum(arr, x, y); cout<<ans; return 0; }
Output
90
Python Code Implementation for Sliding Window Algorithm
def maximum_sum(arr, k):
# length of the array
x = len(arr)
if x < k:
print("Incorrect")
return -1
# sum of first k elements
current_sum = sum(arr[:k])
maximum_sum = current_sum
# remove the first element of previous
# window and add the last element of
# the current window to calculate the
# the sums of remaining windows by
for i in range(x - k):
current_sum = current_sum - arr[i] + arr[i + k]
maximum_sum = max(current_sum, maximum_sum)
return maximum_sum
arr = [20, 10, 30, 40, 20, 10]
k = 3
print(maximum_sum(arr, k))
Output
90
Java Code Implementation for Sliding Window Algorithm
public class Main {
static int maximum_sum(int[] arr,int k){
//length of the array
int x=arr.length;
//length of array(n) must be greater than window size(k)
if(x<k){
System.out.println("Incorrect");
return -1;
}
//sum of first k(window size) elements
int current_sum=0;
for(int i=0;i<k;i++) current_sum+=arr[i];
int maximum_sum=current_sum;
//Also updating the maximum sum to current window sum
// if the current window sum is greater
// than existing maximum sum.
for(int i=k;i<x;i++){
current_sum+=(arr[i]-arr[i-k]);
maximum_sum=Math.max(current_sum,maximum_sum);
}
return maximum_sum;
}
public static void main(String[] args) {
int k=3;
int[] arr={20, 10, 30, 40, 20, 10};
System.out.println(maximum_sum(arr,k));
}
}
Output
90
Time Complexity
The Time Complexity of running this Sliding Window technique algorithm is O(N) as in this approach we run only one loop to compute the maximum_sum, where N is the number of elements present.
Conclusions
The Sliding Window Algorithm is used in a very concentrated manner, where the size of the window for calculating any problem or analysing an algorithm is constant throughout the program. The complexity can then be reduced using this method, and the naive algorithm can be optimised using the Sliding Window Technique. It should always be used when the window size is set. We can implement this algorithm in a variety of ways depending on our needs and the requirements of the issue, such as iterating from left to right or right to left, for example.
Good luck and happy learning!