Reducing complexities with The Sliding Window Algorithm
In this short and precise article, I’ll steer you, how you can slide down the complexity of the program with the help of the sliding window algorithm.
Hold Tight, Let’s get started.
If you can’t fly, then run, if you can’t run, then walk, if you can’t walk, then crawl, but by all means, keep moving. :– Martin Luther King Jr.
What is an Algorithm?
An algorithm can be defined as the set of rules/instructions to achieve some goal in an efficient time.
When you make tea, you follow a certain algorithm.
- Put the teabag in a cup.
- Fill the kettle with water.
- Boil the water in the kettle.
- Pour some of the boiled water into the cup.
- Add sugar (if you prefer).
- Add milk (again if you prefer).
Tea is now ready, so grab the cup and continue learning ;D
In programming, algorithm plays an important role in reducing the time consumption of the program and to give the optimized solution. A single algorithm has the potential of reducing the time that a program takes to solve a problem.
Importance of Time Complexity in Competitive Programming?
Time complexity plays a crucial role in CP. Half of the problem you can crack just by seeing the constraints provided in the questions. The complexity of algorithms will decide whether you will get AC or TLE. When your code is less complex and takes less time to execute for all the test cases, you will get AC otherwise you will end up with TLE (Time Limit Exceeded). To rescue you from this situation many optimized techniques and algorithms are there and today we will discuss one of those technique/ algorithm which is known as The Sliding Window Technique.
What is Sliding Window Algorithm/Technique?
This technique shows you how the nesting of two loops can be converted to a single loop and one can reduce the time complexity drastically. In other words, you can say that the sliding window technique can convert the journey of an algorithm from O(n²) to O(n).
There are 2 variations in the technique:-
- Fixed size window.
- Variable size window.
Now analyze this technique with an example.
Q.) You are given an array of size ’n’ and we aim to calculate the sum of ‘k’ consecutive elements in the array.
Note: To identify the sliding window questions the word Consecutive/Contiguous is the biggest clue to crack the problem.
Consecutive/Contiguous means one after the other, or you can say elements sharing the common border in an array.
Coming back to the question, you are given an array of size let’s say 5.
Input Array:- arr[]={10, 20, 30, 40, 50}
k=3
Output:- 120
Explanation:
10+20+30 = 60
20+30+40 = 90
30+40+50 = 120
so the contiguous array [30, 40, 50] of k=3 elements is 120. Hence 120 is the output of the program.
Let’s analyze the program with the Naïve or Brute Force Approach.
We start with the first index and sum till the kth element. We do it for all possible consecutive blocks or groups of k elements. This method requires nesting of for loop, the outer for loop starts with the starting element of the block of k elements, and the inner or the nested loop will add up till the kth element.
The time complexity of the above code is O(k*n) which will be slow when the input is large.
Now we will discuss the Sliding Window Approach for an optimized solution.
- We will compute the sum of array value till the size of the window is reached i.e. k.
- When the window size is achieved we will update the maximun_sum value.
- After updating the value we will subtract the left end of the window (left most element) and increase the right and left pointer.
The time complexity of the approach is O(n).
You can consider a sliding window as the windowpane of the bus where you can slide the pane left and right.
The below picture will help you to analyze the concept and can help you to imagine is that line.
So, you can see how a sliding window can save you from the nesting of loops and can make your code fast. We will discuss one example on the Fixed Size Window.
Q) First negative of every window of size ‘k’ in an array of size ‘n’?
Example:-
arr[] = {12, -1, -7, 8, 9, -14, 13, 14, 15, -65} size of an array is 10
k = 3
Output:- [ -1, -1, -7, -14, -14, -14, 0, -65 ]
Explanation:-
First Window:- [ 12, -1, -7 ], 8, 9, -14, 13, 14, 15, -65 = -1
Second Window:- 12, [ -1, -7, 8 ], 9, -14, 13, 14, 15, -65 = -1
Third Window:- 12, -1, [ -7, 8, 9 ], -14, 13, 14, 15, -65 = -7
Fourth Window:- 12, -1, -7, [ 8, 9, -14 ], 13, 14, 15, -65 = -14
Fifth Window:- 12, -1, -7, 8, [ 9, -14, 13 ], 14, 15, -65 = -14
Sixth Window:- 12, -1, -7, 8, 9, [ -14, 13, 14 ], 15, -65 = -14
Seventh Window:- 12, -1, -7, 8, 9, -14, [ 13, 14, 15 ], -65 = 0
Eighth Window:- 12, -1, -7, 8, 9, -14, 13, [ 14, 15, -65 ] = -65
Hence the output:- [ -1, -1, -7, -14, -14, -14, 0, -65 ]
The Time Complexity of the above code is O(n) i.e. Linear Time Complexity.
Explanation of above code:-
- Accepting the size of an array ‘n’, window size ‘k’, array elements.
- Defining Queue Data Structure which works on the principle of First In First Out.
- Traversing an array till the window size and if we get -ve value, offer it to the queue.
- Now traversing the array from ‘k’ till the end of the array.
- If our queue is (!empty) then it means we have a -ve number, display it, else display 0.
- Check for the overflow and start offering other -ve values in an array to the queue.
- Lastly, display the contents.
Note:- For the Brute Force Approach the outer loop will run from 0 to (n-k+1), and the inner loop will run from 0 to k. hence the time complexity will be O((n-k+1)*k) which can also be written as O(n*k).
You can see how the sliding window algorithm/ technique slides down the complexity to linear time.
Now coming on to the 2nd variation of the sliding window technique i.e. Variable Size Sliding Window.
What is a Variable Size Sliding Window?
In the above 2 examples we have seen that the size of the window is already provided in the question, but in this method size of the window will not be given rather we have to find something related to it.
Let’s explore these types of questions.
Q) Find the largest subarray with the sum equal to ‘k’?
Observation:- If you read this question carefully you are provided with two hints.
Not able to figure it out yet?
Don’t worry, See the first hint is SUBARRAY which means contiguous/ consecutive, and the other hint is SUM EQUAL TO k.
So Akshat, how these two hints will help us to solve this question with the sliding window technique?
The largest subarray will be the size of the largest window of sum k which we have to find and the question is over.
Example:-
arr[] = {4, 1, 1, 1, 2, 3, 5} size of the array is n=7
k = 5 the sum for which we have to find the largest subarray.
Output:- 4
Explanation:-
4+1 = 5 (size = 2)
1+1+1+2 = 5 (size = 4)
3+2 = 5 (size = 2)
5 = 5 (size = 1)
Note:- All values are contiguous in an array.
Hence the output is 4
Explanation of above code:-
- Summing up the value from the right end till we get the required condition.
- When the condition is reached we will update the max value with the size of the window.
- if the sum exceeds ‘k’ we will reduce the value by subtracting the values from the left side/pane of the window.
- Increase the left and right pointers to move the window till the end of an array.
The time complexity of the above code is O(n) i.e. Linear Time Complexity.
In Brute Force Approach you have to again apply nesting loops which will have the time complexity of O(n²). (You can try it and then compare it with an optimized solution).
By now you must have realized how the sliding window algorithm/ technique will help you, also it is very easy to code there are different questions where you have to apply different data structures along with sliding window for more efficient solutions, one is with Queue Data Structure which I’ve shown to you in the above example.
I’ll be adding some questions resources at the end of the article for you to practice if you are preparing for an interview or any CP competition like ICPC, IOI.
Closing Notes:
Thank you for reading this article so far, also all the best for your future endeavors. I hope this article helped you in understanding this concept, also I hope you all will also become the optimized version of yourself ;).
Stay tuned for more articles.
An investment in knowledge pays the best interest.
View Gist on GitHub :- https://gist.github.com/akshat-fsociety
You all can contact me, in case of doubts:-
LinkedIn:- https://www.linkedin.com/in/akshat-srivastava-4812271a9/
GitHub:- https://github.com/akshat-fsociety
Data-Structure-Algorithms repository:- https://github.com/akshat-fsociety/Data-Structures-Algorithms
Questions (Resources)
- https://www.geeksforgeeks.org/tag/sliding-window/
- https://leetcode.com/problemset/all/?topicSlugs=sliding-window
- https://www.codechef.com/tags/problems/sliding-window
These are some links to practice Sliding Window Technique.
Good Bye!!
