Solve subarray problems FASTER (using Sliding Windows)
Solve subarray problems FASTER (using Sliding Windows)
Save 20% on Interview Prep Courses with Exponent: https://www.byte-by-byte.com/aff/expo…
There are many algorithms that come up frequently in coding interviews, with Sliding Windows being one of the most popular.
In this video, you’ll learn what a sliding window is, how to use it effectively, and I’ll show you two examples of when to use sliding windows in a coding interview.
RESOURCES \u0026 LINKS MENTIONED IN THIS VIDEO:
Coding Interview Questions and Answers Playlist: • Interview Question: FizzBuzz
YOU CAN ALSO FIND ME HERE
Website: https://www.byte-by-byte.com
Twitter: https://twitter.com/ByteByByteBlog
Facebook: https://www.facebook.com/bytebybyteblog
Content
0.3 -> So you go into your coding interview and your interviewer asks
3.16 -> you a question something like this: "I want you to take
5.63 -> an array and find the sum of all subarrays of length
7.92 -> K." Now you figure "That's no problem.
9.65 -> I can do that.
10.25 -> I'll just go through each subarray,
11.88 -> right? I'll iterate over it and compute this up."
14.1 -> So you write some code that iterates over the first K
16.43 -> elements in this case three,
17.79 -> and then you get the sum,
18.95 -> which is six.
19.59 -> Then you iterate over the next three elements and then the
22.37 -> next three elements,
23.41 -> and then the next three elements.
25.03 -> And you sum them each of those up to get your
27.06 -> result. No problem.
28.04 -> But then after all of that,
29.32 -> you still end up failing your interview because your solution was
32.5 -> O(N * K) instead of O(N).
33.99 -> And this is why sliding windows are so important.
36.57 -> Because anytime we're looking at overlapping subways,
39.53 -> sliding windows allow us to optimize our solution.
42.24 -> Let's go back to the example that we were looking at
44.89 -> here. Do you see the problem?
46.4 -> Every time we compute the sum of a subarray,
48.66 -> we compute the sum of those first three values.
51.12 -> Then we compute the sum of the next three values,
53.7 -> but we are actually computing the sum of these two values
57.12 -> in the middle twice to get to the sum of six
59.6 -> for this first subarray and nine for the second subarray.
63.09 -> We don't actually need to recompute everything.
66.07 -> All we need to do is look at the difference between
69.06 -> these two summaries.
70.37 -> And in this case,
71.39 -> the only thing that actually changes is the first and last
74.88 -> values. If we compare the sum of the first summary to
77.79 -> the sum of the second summary,
79.5 -> the only difference between these is that first and last value
82.95 -> in the first summary,
84.21 -> we include the one,
85.47 -> but we do not include the four.
87.54 -> And then in the second summary,
89.19 -> we do not include the one,
90.75 -> but we do include the four.
92.58 -> And so to get from six to nine,
94.74 -> we can say six minus one,
97.74 -> plus four,
99.33 -> because we excluded the one.
101.25 -> And we included the four that way by just doing a
104.1 -> little bit of arithmetic,
105.45 -> we were able to get that new sum without having to
108.24 -> sum up any of these values in the middle.
110.49 -> If we consider a case where K is equal to five,
113.01 -> then this effect is even more obvious because our first sub-array
116.46 -> we're summing up all these values.
118.65 -> And then our second sub-array,
120.03 -> we're summing up all these values.
121.98 -> And as you can see,
122.7 -> there's a large overlap between the two submarines.
125.46 -> So it's totally unnecessary for us to sum up all those
128.43 -> values. Multiple times.
129.87 -> All we need to do is subtract this first value and
133.44 -> add this last value to get from the sum of one
136.11 -> sub-array to the summit,
137.34 -> the next summary,
138.84 -> and this is the fundamental idea behind a sliding window with
141.84 -> a sliding window,
142.56 -> we start with our initial sub-array,
144.45 -> which is that initial window.
145.98 -> And then we slide that along our rep,
149.25 -> we remove that initial value and we add that next value.
152.4 -> And we keep doing that,
153.6 -> moving through the array,
154.86 -> which allows us to compute all of those suns in linear
157.8 -> time. So how do we apply this concept back to that
160.79 -> original question where we want to find the sum of each
163.79 -> subarray of length?
164.93 -> Okay, well,
165.59 -> first we're going to sum up that initial summary and we're
168.79 -> going to get this value of six,
170.46 -> which we add to our results.
171.99 -> Now we slide our window by one and we compute this
174.66 -> value in constant time by subtracting one and adding four and
178.06 -> getting done.
178.96 -> We repeat this process again,
180.76 -> and we ended up with 12 as our next value by
182.89 -> removing the two and adding five.
185.29 -> And finally,
185.86 -> for our last window,
186.73 -> we slide one more time.
188.05 -> We remove the three and we add six and we get
190.45 -> 15 in terms of actually coding this up.
193.6 -> Here's a simple example of what the code might look like.
196.36 -> We start by computing,
197.44 -> the sum of that initial sub-array and adding that to our
200.38 -> result. And then we iterate through all of the remaining subarrays.
204.03 -> And as we do that,
204.92 -> we remove that initial element and we add the next element
207.99 -> and then append it to our result.
209.72 -> Now, what we just covered is the simplest form of a
212.34 -> sliding window,
213.23 -> a fixed size sliding window.
214.77 -> In this case,
215.47 -> our window is staying the same size throughout our window is
218.41 -> always size cap,
219.24 -> but there's also another type of sliding window.
221.65 -> And that is a dynamically sized sliding window.
224.01 -> And this is really useful for us when we want to
226.24 -> find the largest or smallest subarray,
228.19 -> right? That matches some sort of condition.
230.37 -> Let's say,
230.9 -> for example,
231.54 -> that we wanted to find the shortest summary with the sum
234.25 -> that was greater than or equal to X.
235.99 -> Here's a simple example of what this might look like in
238.5 -> this case.
239 -> We have this array and X is equal to seven,
240.9 -> and we can see that there are multiple different subarrays that
243.86 -> would sum up to greater than or equal to seven.
245.98 -> For example,
246.59 -> we could just sum up the whole thing.
248.26 -> And that would sum up to greater than seven.
250.27 -> We could also sum up three,
251.5 -> four, which would be exactly equal to seven.
254.14 -> We could sum up five,
255.1 -> six, which would be greater than seven.
257.59 -> All of these would be valid.
258.97 -> However, we want to find the one that is shortest.
261.37 -> And so in this case,
262.3 -> our shortest it's going to be a flight two,
264.37 -> which would either be this sub-array,
266.44 -> this sub-array or this sub-array now,
269.44 -> how are we going to use our dynamically sized sliding window
273.06 -> here? We don't know what size the summary needs to be.
276.24 -> And so our dynamic sliding window allows us to start small
279.71 -> and expand and expand and expand until we match the condition
283.4 -> that we need.
284.2 -> Once we find a subarray rate that matches our sum,
287.16 -> then we try and contract again from the other side to
290.27 -> get, what is that minimally size summary that has a sum
293.83 -> that is greater than X.
295.39 -> What that looks like in this case is that we're going
297.49 -> to start by looking at this sub-array one and we'll track
300.52 -> our sum,
301 -> which in this case is equal to one.
303.1 -> One is not greater than X.
304.93 -> And so this summary is not valid.
306.85 -> So we need to expand it.
309.1 -> We expand our summary out to link to,
311.92 -> and now our sum is three,
313 -> but three is still not greater than seven.
314.98 -> So we need to keep expanding.
316.81 -> We expand to length three,
318.04 -> we're still not there.
318.94 -> So we need to expand further.
320.8 -> We expand one more time to like four.
323.08 -> And now we found a sum of 10,
324.49 -> which is greater than seven.
326.08 -> So now the minimum length of a summary that we have
328.51 -> found so far is four.
330.52 -> And we can keep track of that,
332.32 -> but we don't know if that is the smallest separate.
334.76 -> So now we have to contract again.
336.94 -> We do that by moving the tail end of our summary
339.19 -> forward, essentially like a caterpillar.
341.56 -> And then we follow this same strategy that we were doing
344.35 -> before. So we subtract the one from our result to get
347.65 -> nine as our sum,
348.59 -> that is still greater than seven.
350.62 -> So now we found a sub-array where the length is three,
353.82 -> but it is still greater in some than seven.
356.35 -> The sum is not.
357.23 -> So now we update our minimum length to a minimum length
360.49 -> of three.
361.07 -> When we contract again,
362.52 -> we find that our sum is seven because we subtracted two
365.78 -> from the nine and that is still greater than or equal
368.9 -> to our X.
369.53 -> So we've actually found an even better solution to our problem,
372.86 -> which is minimum length of two.
374.72 -> Can we contract any further than this?
376.91 -> Maybe. I mean,
377.66 -> we don't really know,
378.35 -> right? So let's try it.
379.97 -> So now when we did that contraction,
381.83 -> our sum is four,
382.73 -> which is less than the seven minimum.
384.89 -> And so now what we have to do is we're going
386.78 -> to have to expand again,
388.46 -> right? Our minimum length is not one because this sub-array is
391.73 -> not a valid summary.
393.08 -> So we'll start expanding again to find another sub-array that has
396.44 -> a sum of at least seven.
398.18 -> When we expand out to include the five,
400.04 -> we've now found another sub-array with some greater than seven,
403.43 -> and it's not any shorter than our previous sub-array.
406.31 -> So this doesn't actually improve our result.
408.98 -> And we'll keep doing this until we get to the end
410.87 -> of the array.
411.38 -> But in this case,
412.37 -> as you can tell,
413.39 -> our best answer is going to be two.
416.39 -> Let's take a quick look at the code for this one
418.29 -> as well.
419 -> We're going to start by initializing our start and end,
421.46 -> which are going to be the range of our current sub-array.
425.48 -> And then what we're going to do is iterate from start
428.62 -> to end,
429.05 -> we're going to keep expanding our end out.
431.61 -> And then each time we expand it,
433.51 -> we're going to check whether the current sum is greater than
437.15 -> or equal to X.
437.96 -> If the current sum is greater than or equal to X,
440.8 -> that means that we want to start contracting that backend,
444.38 -> that tail end or the start of our subarray.
447.23 -> And so we'll go through this inner wild loop and keep
449.75 -> contracting. As long as our current sum is greater than or
452.9 -> equal to X,
454.07 -> once it's no longer,
455.45 -> we will track that minimum value.
457.52 -> And then we'll expand our end out again.
459.59 -> And again,
460.04 -> we repeat this process in sort of a caterpillar like way
463.61 -> until we get to the end of our array.
465.92 -> Now what's the complexity of this solution because our naive solution
469.8 -> to this problem would be basically to compute the sum of
472.82 -> every single sub-array and see which one is shortest,
475.78 -> where the sum is greater than packs the complexity for doing
479.06 -> that. They're going to be N^2 different subarrays,
481.89 -> and to compute the sum of each one is going to
484.25 -> take us O(N) time.
485.45 -> So our total complexity would be O(N^3).
487.58 -> Now, when we do our sliding window,
489.39 -> you can kind of think about it in terms we basically
492.02 -> have each turn.
492.83 -> We're either moving the start pointer or we're moving the end
496.02 -> point. And each of those is moving in one direction.
498.71 -> And each of those is moving at at least one step
501.09 -> per term.
502.04 -> So in total,
502.69 -> both of those pointers move from the beginning of RRA to
505.7 -> the end of RA,
506.42 -> that means that our complexity for this problem is basically two
509.95 -> times N or O(N).
510.8 -> That's obviously a huge improvement on our time complexity.
514.14 -> And that's really the beauty of sliding windows,
516.82 -> sliding windows allow us anytime we're considering multiple subarray to avoid
521.2 -> doing those repeated calculations inside of the array,
524.69 -> rather than having to consider every possible sub-array,
527.57 -> we're able to expand and contract and consider how do those
531.11 -> separates relate to each other and really optimized to get the
535.2 -> optimal solution to a problem.
537.09 -> Now, sliding windows are really just one of the patterns that
539.43 -> you need to be familiar with to be successful at solving
542.34 -> string and array problems in a coding interview.
544.68 -> I actually put together another video that covers five of the
547.35 -> most common string patterns that you need to know for your
550.2 -> interview. So I'd encourage you to go over and check that
552.63 -> out next.
Source: https://www.youtube.com/watch?v=GcW4mgmgSbw