Hey curious people👋! Have you ever felt so good after writing an algorithm that not only solves a problem but solves it efficiently? In this blog, we'll learn about an algorithm that'll help you get that feeling more often! Sliding Window Technique(SWT) - I understand this algorithm as one that helps improve the time complexity of a solution(generally for problems dealing with sequential and iterable data structures like an array) from O(N²) to O(N) and if you don't understand Time Complexity, just know that it helps improve your solution so that it runs faster.
What is SWT?
According to most definitions, SWT is a way of converting some brute force(mostly O(N²))) algorithms to a linear(O(N)) algorithm.
Is it helpful?
In an interview, improving an algorithm from O(N²) to O(N) is a great deal(well...at least for me😅).
How to do it?
To understand how to do it, let's look at a problem, at first we will think about a brute force solution and then improve it by applying SWT. Before that let me give you a basic idea of how we apply SWT(this might not make sense now, but definitely will during solving the problem!).
Let's suppose we have an array and we want to find the largest element in the array. The solution might be to look at every element and keep track of the largest element. To put it in the SWT way, it might look something like this:👇
Now you might have guessed it, The window slides(did it click?💡) from left to right, we look at the value check if it is the largest element we have seen and this continues until the window reaches the end of the array. The window might be of any size depending on the problem we are dealing with, it can be one(or any number of elements) elements long, or it can be of variable size. The window size can either be fixed or dynamic.
The Problem
Given an array of N positive integers, find the maximum sum of 3 consecutive elements
The brute force approach
The first solution that comes to my mind is to find every possible sub-array of 3 consecutive elements and find their sum and keep track of the maximum one. We'll need two nested loops for this, let's see this algorithm in code.
let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0; //to keep track of maximum sum.
for (let i = 0; i < arr.length - 3 + 1; i++){
//Initializing sum
let sum = 0;
//Adding 3 elements starting from i
for (let j = 0; j < 3; j++){
sum = sum + arr[i + j];
}
//Storing the maximum sum
maxSum = Math.max(sum,maxSum);
}
console.log(maxSum);
The Time Complexity of this algorithm is O(N*3), it could be worse if it was a bigger set of elements instead of 3.
The SWT approach
Now, let's see how the SWT approach works.
Now what we want to do is have a window of size 3, keep count of its sum and keep track of the maximum sum as it slides to right. Now let's visualise what will happen if the window moves one element to the right. What we are actually doing is adding the 4th element to the sum and subtracting the 1st element, and repeating the same until the window reaches the end of the array. Let's see how that will look like in code.
let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0; //to keep track of maximum sum.
let sumOfWindow = 0; //to keep track of sum of the window.
let windowSize = 0;
for (let i = 0; i < arr.length + 1; i++){
if(windowSize == 3){
console.log('current windows sum is');
console.log(sumOfWindow);
//storing the maximum sum
maxSum = Math.max(maxSum, sumOfWindow);
//deleting the end element of the window
sumOfWindow = sumOfWindow - arr[i - 3];
windowSize--;
}
//adding elements to the window.
sumOfWindow = sumOfWindow + arr[i];
windowSize++;
}
console.log("The maximum sum is: " + maxSum);
Voila! That's in a single loop, that means O(N) time complexity! ahem..To use fewer loops, use more brain aaaaand probably some more lines of code(not always).
There you have it! Sliding Window Technique!
When to use it?
I try to use it generally when I see problems that have something to do with consecutive elements of an iterable data structure like arrays or strings(For ex: max continuous subarray, longest non-repeating substrings).
Now that you know about SWT, would you try solving this problem in hackerrank?.keep in mind that the size of the window can be dynamic, it doesn't always have to be a fixed number like three.
If you liked this blog consider buying me a coffee😊 or support me in patreon.
check out other blogs in this series.👇
Top comments (3)
Actually both of the shown algorithmns have linear complexity O(n) (the number of operations depends directly on the number of array elements n). If you count the number of operations, for the "brute-force" algorithm you will need 9 additions for each array element (excluding the outer for loop), while for the second one you will need 4 additions and 1 substraction for each array element. You could, however, optimize the brute-force algorithm to need 6 additions for each array element:
const arr = [1, 3, 5, 6, 2, 7, 8]; let maxSum = 0; //to keep track of maximum sum. for (let i = 0; i < arr.length - 3 + 1; i++){ //Initializing sum let sum = arr[i]; //Adding 3 elements starting from i for (let j = i+ 1; j < i + 3; j++){ sum = sum + arr[j]; } //Storing the maximum sum maxSum = Math.max(sum,maxSum); } console.log(maxSum);Great Article!
Thanks a lot!😊👊