Coding Patterns: Sliding Window
If you haven’t looked at my previous post on Binary Search, then please have a look at it. Sliding Window comes in handy when attending any coding Interview in any of the big giant MNC’s(FAANG). I have encountered these patterns many times in my past coding interviews.
- This method is usually used in array/list, whenever you are asked to calculate anything like minimum or maximum of continues subsets of an array of fixed length.
- This consists of calculating a value for the given length by moving our widow element by element until we reach the array end.
Let’s consider a question and see how we solve it in OLD SCHOOL way and how sliding window makes it much better.
Given an array of positive numbers and a positive number ‘k’
find the maximum sum of any contiguous subarray of size ‘k’Input: [5, 2, 6, -2, 10, 15], k=3
Output: 23
Explanation: Subarray with maximum sum is [-2, 10, 15]Input: [-10, 5, 2, 4, 5], k=2
Output: 9
Explanation: Subarray with maximum sum is [4, 5]
- I think there’s no need to explain the code above, as it pretty straight forward.
Let’s talk on what’s wrong with using the above method
- As you can observe we are two loops, one inside another so the time complexity bumps up to O(N * K), and its gonna hit the performance when our ‘K’ value is huge.
Let’s Solve Using Sliding Window
Before getting into the solution lets see what is the inefficiency in the above method, that is for any two consecutive two sub-arrays of size 5‘K’, the overlapping part will contain 4 elements(K-1).
- As you can see, there are four overlapping elements between the subarray (indexed from 0–4) and the subarray (indexed from 1–5). Can we somehow reuse the sum we have calculated for the overlapping elements?
- The better way would be to imagine each contiguous subarray as a sliding window of ‘5’ size, and we move that window by one element in each loop.
- Visualize the below picture, where K =3.
So now, as you have gotten a view on how sliding windows works, let’s use it to solve the question introduced earlier to you above.
Solution using Sliding Window
Input: [1, 2, 6, 4, 10, 15], k=3
If you observe closely, you will realize that to calculate the sum of a contiguous subarray we can utilize the sum of the previous subarray. For this, consider each subarray as a Sliding Window of size ‘k’. To calculate the sum of the next subarray, we need to slide the window ahead by one element. So to slide the window forward and calculate the sum of the new position of the sliding window, we need to do two things:
- Subtract the element going out of the sliding window i.e., subtract the first element of the window.
- Add the new element getting included in the sliding window i.e., the element coming right after the end of the window.
How is this better than the previous approach?
- As you can observe we have reduced from two loops to one loop, so our time complexity reduced to O(N).
How to Identify the Pattern:
wherever we see a question where we have to deal with continuous sub-array of some size, and we have to find calculate some value on those sub-arrays, this can be used.
Before we end this, this is just to get you introduced to the topic, to get comfortable solve more and more, you can solve these questions.
Leetcode questions(solve these).
https://leetcode.com/problems/minimum-window-substring/
https://leetcode.com/problems/longest-substring-without-repeating-characters/
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
https://leetcode.com/problems/find-all-anagrams-in-a-string/
Whats next?
- Will be covering topics like dp(Dynamic programming), two pointers, graphs, basically things you will need for your next technical interview.
