Sliding windows are one of the mosts common patterns that you need to know to solve Array and String problems. In this video, you'll learn how to use this algorithm effectively for your coding interviews.
Transcript
So you go into your coding interview and your interviewer asks you a question something like this:
“I want you to take an array and find the sum of all subarrays of length K.”
Now you figure “That's no problem. I can do that. I'll just go through each subarray, right? I'll iterate over it and compute this up.”
So you write some code that iterates over the first K elements in this case three, and then you get the sum, which is six. Then you iterate over the next three elements and then the next three elements, and then the next three elements. And you sum them each of those up to get your result. No problem. But then after all of that, you still end up failing your interview because your solution was O(N * K) instead of O(N).
And this is why sliding windows are so important. Because anytime we're looking at overlapping subways, sliding windows allow us to optimize our solution.
Let's go back to the example that we were looking at here. Do you see the problem? Every time we compute the sum of a subarray, we compute the sum of those first three values.
Then we compute the sum of the next three values, but we are actually computing the sum of these two values in the middle twice to get to the sum of six for this first subarray and nine for the second subarray.
We don't actually need to recompute everything. All we need to do is look at the difference between these two summaries. And in this case, the only thing that actually changes is the first and last values.
If we compare the sum of the first summary to the sum of the second summary, the only difference between these is that first and last value in the first summary, we include the one, but we do not include the four. And then in the second subarray, we do not include the one, but we do include the four. And so to get from six to nine, we can say six minus one, plus four, because we excluded the one.
And we included the four that way by just doing a little bit of arithmetic, we were able to get that new sum without having to sum up any of these values in the middle. If we consider a case where K is equal to five, then this effect is even more obvious because our first sub-array we're summing up all these values.
And then our second subarray, we're summing up all these values. And as you can see, there's a large overlap between the two submarines. So it's totally unnecessary for us to sum up all those values multiple times. All we need to do is subtract this first value and add this last value to get from the sum of one subarray to the sum of the next subarray.
And this is the fundamental idea behind a sliding window.
With a sliding window, we start with our initial sub-array, which is that initial window. And then we slide that along our array, we remove that initial value and we add that next value. And we keep doing that, moving through the array, which allows us to compute all of those sums in linear time.
So how do we apply this concept back to that original question where we want to find the sum of each subarray of length?
Okay, well, first we're going to sum up that initial subarray and we're going to get this value of six, which we add to our results. Now we slide our window by one and we compute this value in constant time by subtracting one and adding four and getting done.
We repeat this process again, and we ended up with 12 as our next value by removing the two and adding five. And finally, for our last window, we slide one more time. We remove the three and we add six and we get 15 in terms of actually coding this up.
Here's a simple example of what the code might look like.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def fixed_sliding_window(arr: List[int], k: int) -> List[int]: # Sum up the first subarray and add it to the result curr_subarray = sum(arr[:k]) result = [curr_subarray] # To get each subsequent subarray, add the next value in # the list and remove the first value for i in range(1, len(arr)-k+1): curr_subarray = curr_subarray - arr[i-1] curr_subarray = curr_subarray + arr[i+k-1] result.append(curr_subarray) return result |
We start by computing the sum of that initial sub-array and adding that to our result.
And then we iterate through all of the remaining subarrays. And as we do that, we remove that initial element and we add the next element and then append it to our result.
Now, what we just covered is the simplest form of a sliding window, a fixed size sliding window. In this case, our window is staying the same size throughout. Our window is always size X,
But there's also another type of sliding window, and that is a dynamically sized sliding window.
This is really useful for us when we want to find the largest or smallest subarray that matches some sort of condition.
Let's say, for example, that we wanted to find the shortest subarray with the sum that was greater than or equal to X.
Here's a simple example of what this might look like in this case.
We have this array and X is equal to seven, and we can see that there are multiple different subarrays that would sum up to greater than or equal to seven. For example, we could just sum up the whole thing. And that would sum up to greater than seven. We could also sum up three, four, which would be exactly equal to seven. We could sum up five, six, which would be greater than seven. All of these would be valid.
However, we want to find the one that is shortest. And so in this case, our shortest it's going to be of length two, which would either be [3,4], [4,5] or [5,6].
Now how are we going to use our dynamically sized sliding window here?
We don't know what size the summary needs to be. And so our dynamic sliding window allows us to start small and expand and expand and expand until we match the condition that we need. Once we find a subarray that matches our sum, then we try and contract again from the other side to get what is that minimally size subarray that has a sum that is greater than X.
NOTE: Recommend watching the video starting at 3:50 for visuals that go along with the explanation.
What that looks like in this case is that we're going to start by looking at this subarray one and we'll track our sum, which in this case is equal to one. One is not greater than X. And so this summary is not valid. So we need to expand it.
We expand our summary out to the two and now our sum is three, but three is still not greater than seven.
So we need to keep expanding. We expand to length three, we're still not there. So we need to expand further. We expand one more time to like four. And now we found a sum of 10, which is greater than seven.
So now the minimum length of a summary that we have found so far is four. And we can keep track of that, but we don't know if that is the smallest separate. So now we have to contract again. We do that by moving the tail end of our summary forward, essentially like a caterpillar. And then we follow this same strategy that we were doing before.
So we subtract the one from our result to get nine as our sum, that is still greater than seven. So now we found a sub-array where the length is three, but it is still greater in some than seven. The sum is not. So now we update our minimum length to a minimum length of three. When we contract again, we find that our sum is seven because we subtracted two from the nine and that is still greater than or equal to our X.
So we've actually found an even better solution to our problem, which is minimum length of two.
Can we contract any further than this? Maybe. I mean, we don't really know, right? So let's try it. So now when we did that contraction, our sum is four, which is less than the seven minimum. And so now what we have to do is we're going to have to expand again?
Our minimum length is not one because this subarray is not a valid subarray. So we'll start expanding again to find another sub-array that has a sum of at least seven. When we expand out to include the five, we've now found another sub-array with some greater than seven, and it's not any shorter than our previous sub-array. So this doesn't actually improve our result.
And we'll keep doing this until we get to the end of the array. But in this case, as you can tell, our best answer is going to be two.
Let's take a quick look at the code for this one as well.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def dynamic_sliding_window(arr: List[int], x: int) -> int: # Track our min value min_length = float('inf') # The current range and sum of our sliding window start = 0 end = 0 current_sum = 0 # Extend the sliding window until our criteria is met while end < len(arr): current_sum = current_sum + arr[end] end = end + 1 # Then contract the sliding window until it # no longer meets our condition while start < end and current_sum >= x: current_sum = current_sum - arr[start] start = start + 1 # Update the min_length if this is shorter # than the current min min_length = min(min_length, end-start+1) return min_length |
We're going to start by initializing our start and end, which are going to be the range of our current subarray.
Then what we're going to do is iterate from start to end, we're going to keep expanding our end out. And then each time we expand it, we're going to check whether the current sum is greater than or equal to X. If the current sum is greater than or equal to X, that means that we want to start contracting that backend, that tail end or the start of our subarray.
And so we'll go through this inner while loop and keep contracting. As long as our current sum is greater than or equal to X, once it's no longer, we will track that minimum value. And then we'll expand our end out again. And again, we repeat this process in sort of a caterpillar like way until we get to the end of our array.
Now what's the complexity of this solution because our naive solution to this problem would be basically to compute the sum of every single sub-array and see which one is shortest, where the sum is greater than packs the complexity for doing that. They're going to be N^2 different subarrays, and to compute the sum of each one is going to take us O(N) time.
So our total complexity would be O(N^3). Now, when we do our sliding window, you can kind of think about it in terms we basically have each turn. We're either moving the start pointer or we're moving the end point. And each of those is moving in one direction. And each of those is moving at at least one step per term.
So in total, both of those pointers move from the beginning of array to the end of the array, that means that our complexity for this problem is basically two times N or O(N). That's obviously a huge improvement on our time complexity. And that's really the beauty of sliding windows, sliding windows allow us anytime we're considering multiple subarray to avoid doing those repeated calculations inside of the array.
Rather than having to consider every possible sub-array, we're able to expand and contract and consider how do those separates relate to each other and really optimized to get the optimal solution to a problem. Now, sliding windows are really just one of the patterns that you need to be familiar with to be successful at solving string and array problems in a coding interview.
I actually put together another video that covers five of the most common string patterns that you need to know for your interview.
So I'd encourage you to go over and check that out next.
