Sliding Window Algorithm for Tech Interviews - Full Course

[00:00] The sliding window algorithm is a [00:02] powerful technique used to optimize [00:04] problems involving arrays or strings by [00:07] converting nested loops into a single [00:09] pass. This course is designed to help [00:12] you master this essential pattern, [00:14] providing you with the intuition needed [00:16] to tackle common technical interview [00:18] challenges. Alvin created this course. [00:21] Hey programmers, and welcome to our [00:23] course on the sliding window algorithm. [00:25] If you're preparing for technical [00:27] interviews and want to master this [00:28] common topic, then you're in the right [00:30] place. [00:31] If we haven't met before, hey, I'm [00:33] Alvin. I'm an ex-Google software [00:34] engineer, and for the last decade, I've [00:36] taught thousands of engineers how to ace [00:38] their interviews and land their dream [00:40] job. [00:41] In the next 2 hours, I'll teach you [00:42] everything you need to know about the [00:44] sliding window algorithm. That means [00:46] we'll cover both the fixed-size and [00:48] variable-size versions of the algorithm. [00:51] In this course, we'll learn by [00:52] completing a series of problems, the [00:55] same problems that you could see on your [00:57] tech interviews. Don't worry, though. [01:00] I've specifically chosen each problem so [01:02] that it ramps up gently. [01:04] We'll start with the basics, and then [01:06] slowly increase the difficulty so that [01:08] you never feel lost. By the end of the [01:10] course, you'll be solving some pretty [01:12] advanced problems. For each problem, [01:14] we'll use a two-step approach to [01:16] learning. First, we'll come up with a [01:18] plan on the whiteboard. I think [01:20] visualizing algorithms is really key to [01:22] understanding them. So, here's where [01:24] we'll illustrate the steps of our logic [01:26] and address any edge cases. [01:28] From there, we'll head into my editor, [01:30] where we'll implement the code and pass [01:32] those test cases. [01:34] I'll be coding in Python, but you can [01:36] feel free to follow along in your [01:37] favorite language. [01:39] All right, I'm super excited to teach [01:41] you sliding window. So, without any [01:43] further delay, let's jump into our first [01:44] problem. [01:46] Hey programmers, Alvin here. Right now, [01:48] I want to go over the approach we can [01:49] use for this max subarray sum size K [01:51] problem. [01:52] So, in this problem, we're going to need [01:53] to learn a new strategy. What does this [01:55] problem asking us to do? We're we're to [01:57] take two different inputs. We're going [01:58] to take in an array of some numbers as [02:01] well as a size K, which is just another [02:03] number. [02:04] Here, what we want to do is consider sub [02:06] arrays of size K. So, because right now [02:08] K is four, it means I look at sub arrays [02:10] with four elements inside. I do bear in [02:13] mind that a sub array is going to be a [02:14] continuous a collection of four elements [02:17] here. So, here I have highlighted one [02:19] possible sub array. [02:21] If I consider the sum of these elements [02:23] in the sub array, their sum is 33. What [02:26] I want to do is consider all such sub [02:28] arrays with four elements. For example, [02:30] this sub array at the very front has a [02:32] sum of 16. [02:34] This sub array somewhere in the middle [02:35] has a total sum of 43. What I want to do [02:38] is return the maximal sum I can get uh [02:41] with any sub array of length four. The [02:43] answer here would indeed be the 43. [02:46] That's the biggest sum of sub arrays uh [02:48] that contain four elements. [02:50] All right. So, let's start discussing a [02:52] strategy for this one. It's really [02:54] important that we do notice that we [02:55] don't need to consider every possible [02:57] sub array of any size. What we want to [02:59] do is only consider sub arrays of this [03:01] target size. Here, our target is four. [03:03] So, what I can do is just start the very [03:05] beginning of the array and move this [03:07] window, right? So, here I have the first [03:08] four elements. After that, I want to [03:10] consider the next four elements, and so [03:13] on and so forth. [03:15] And that of course gives us our classic [03:16] sliding window strategy, which is what [03:19] we're going to explore in this upcoming [03:20] module. So, let's discuss the logic that [03:22] we're going to use for the sliding [03:24] window algorithm. [03:25] So, we're going to start our window at [03:26] the very beginning of the array. That [03:28] makes sense. And because in this problem [03:30] we want to consider uh the maximum sum, [03:32] I'm going to create a variable to track [03:34] the maximum I've seen so far. This [03:36] should be very familiar. You can go [03:38] ahead and initialize this variable to [03:39] something logical like negative [03:41] infinity, right? Cuz I want it to be [03:43] replaced over time. Negative infinity is [03:45] never going to win when I compare a [03:47] maximum. [03:48] So, now that I'm looking at this very [03:50] first window containing my four [03:52] elements, I want to just take their sum. [03:54] So, in other words, just add up 1 + 4 + [03:57] 1 + 10. That gives me the sum of 16. I [04:00] should just compare this 16 to my [04:03] current maximum. And of course, I should [04:05] replace that negative infinity because [04:07] 16 is greater than negative infinity. [04:10] So, right now the max sum I have so far [04:12] is 16. At this point, I could just slide [04:14] my window. Now, I look at the next four [04:16] elements. Again, just add up all the [04:18] elements inside. [04:19] 4 + 1 + 10 + 25 gives me a sum of 40. [04:24] And I do that max value logic. I compare [04:26] 40 against my maximum sum of 16. 40 is [04:29] greater, so I go ahead and replace that [04:31] as the max sum. [04:33] Slide my window over to the right a [04:34] little bit. And again, I add up these [04:36] four elements. [04:38] You take the sum of 1 + 10 + 25 + 3, you [04:41] get 39. [04:43] 39 is not bigger than my maximum sum so [04:45] far, so I don't replace it. You should [04:47] still move your window over, though. [04:49] Looking at my next window, I do 10 + 25 [04:52] + 3 + 5. That gives me a sum of 43. And [04:56] of course, 43's bigger than my current [04:57] maximum sum of 40, so I replace it with [05:00] the 43. [05:01] This algorithm will just continue for [05:02] the remaining elements. This next [05:05] sliding window has a sum of 33, which is [05:08] not going to replace my 43. [05:10] And finally, this very last window has a [05:12] total sum of 34, which is not going to [05:14] replace my 43. Because I'm done looking [05:17] at all possible sub arrays of size four, [05:21] I can just return this as my final [05:23] answer, right? 43 is the maximum sum of [05:25] any sub array containing exactly four [05:27] elements. [05:29] So, let's go ahead and start to think [05:30] about the complexity of this algorithm, [05:32] right? So, I'll define my terms. Here, I [05:35] have two inputs, right? I have my [05:36] numbers array, as well as my size K. [05:40] So, let's say N is the length of the [05:41] array. [05:42] Let's say that K is the sub array size [05:44] that we're targeting. [05:46] What I want to do is start thinking [05:47] about my possible pieces of my [05:49] complexity here. So, the first part [05:51] would be the number of sub-arrays, [05:53] right? How many sub-arrays am I looking [05:55] at? In other words, how many windows do [05:57] I have to look at here? [05:58] I'm going to tell you that the number of [06:00] sub-arrays is given by roughly n minus [06:03] k. So, how can we reason that out over [06:05] here? [06:06] Well, of course, the sub-arrays are [06:07] really just every little window I looked [06:09] at over here. [06:10] We know that we're going to slide this [06:12] window throughout the nums array. And [06:14] so, think of this total number of [06:16] elements, total number of elements in [06:18] our nums array, we just said was n. [06:21] And of course, you're going to be [06:22] sliding this window to the right, like [06:24] so. [06:25] And as you slide it, this is the [06:26] farthest you can move it to the right, [06:28] right? Because of course, your window [06:30] that you consider contains k elements. [06:33] That'd be over here. [06:35] So, you really need to stop sliding your [06:37] window once you're k elements from the [06:39] right edge of the array. In other words, [06:41] you can't look outside of bounds here, [06:43] right? For example, if you had your [06:45] window starting at the element zero, [06:48] then your last two elements are going to [06:49] be out of bounds. So, that wouldn't be a [06:51] valid sub-array to consider. That's why [06:53] I'm saying you need to stop sliding your [06:54] window once you're k elements from the [06:56] end of the array. [06:58] So, the total number of sub-arrays you [06:59] consider is really just n minus k. [07:02] All right. And beyond that, if that's [07:05] going to be the number of sub-arrays we [07:06] look at, how much work do we do per [07:09] sub-array? That'd be the next piece of [07:11] my complexity here. Well, the amount of [07:13] work you do per sub-array is really [07:14] going to be k. What does that really [07:16] mean? Well, whenever we looked at some [07:18] window, for example, the one I have on [07:20] the screen right now, you had to add up [07:22] all of the elements inside of it. And of [07:24] course, I know there going to be k [07:26] elements inside of that little window. [07:28] So, you need to do k work for every [07:30] sub-array you consider. [07:33] So, how can you get the total time [07:34] complexity from this? Well, you could [07:35] just multiply these two quantities [07:37] together. [07:38] So, your complexity in its Its form is [07:40] going to be n minus k times k. This [07:43] quantity is just the number of sub [07:45] arrays multiplied by the amount of work [07:47] per sub array. [07:49] Let's go ahead and simplify this time [07:50] complexity and to do that you can just [07:52] start by multiplying that x across your [07:54] terms here. [07:56] So if I multiply those things, I get nk [07:59] minus kk. [08:01] Now we can simplify this even more. [08:03] Given in the problem, they tell us that [08:05] n is greater than or equal to k. In [08:08] other words, the size of the sub arrays [08:10] you're going to be looking at, it can't [08:11] ever be bigger than the original array, [08:14] right? Cuz that really wouldn't make any [08:15] sense. [08:16] And because we have this guarantee that [08:18] n is greater than or equal to k, we can [08:20] simplify even further. [08:22] This means that nk is certainly bigger [08:25] than kk. [08:26] And so I can drop the kk from my [08:28] complexity. [08:29] So right now I'm saying that the time [08:30] complexity of this algorithm so far is [08:33] just O of nk. [08:35] And this is a fine strategy in that it [08:37] gives us the correct result, but it's [08:38] not the optimal strategy. Really, this [08:40] is just our naive sliding window time [08:42] complexity. So I want to actually [08:44] discuss an algorithm that can perform [08:46] faster than this. And don't worry, we're [08:48] still going to utilize sliding window, [08:50] but we're going to manipulate things a [08:51] little bit here. [08:53] And so let's go ahead and think about uh [08:55] the logic here a bit. So when I consider [08:57] a window like this one for example, I [08:59] know I have to add up all of the [09:01] elements inside. And that definitely [09:03] contributed to my complexity, right? [09:05] That's where the k comes from in my [09:07] complexity of nk right now. [09:10] So after I consider uh this sub array, [09:12] when I slide my window to the right, the [09:14] next sub array I consider is this one. [09:17] Here I'm going to mark it in green. [09:20] And I'll also have arrows pointing to [09:22] the elements I need to add up for that [09:24] little window. [09:25] Also in green. [09:27] It's pretty clear to me that I have a [09:29] lot of overlap in these two windows, [09:32] right? Everything in the middle [09:33] overlaps. And so what I want to do is [09:36] avoid uh recomputing those into the sum. [09:40] Right? [09:41] And so, how can we actually redesign the [09:42] algorithm here? It's going to start in a [09:44] very similar way. You're going to begin [09:45] with your window all the way to the [09:47] left. That makes sense. [09:48] And what you want to do over time is [09:50] also track a current sum. So, previously [09:52] I just had a max sum. Now, I want a [09:54] current sum. Right? And because you're [09:56] at the very beginning of the algorithm, [09:58] just go ahead and uh find the total sum [10:01] of this initial window. So, just do 1 + [10:03] 4 + 1 + 10. That gives you a total sum [10:06] of 16. And from here, you just continue [10:08] your basic max value logic. Because I [10:10] don't have a maximum stored so far, this [10:13] current sum of 16 is going to be my [10:15] initial maximum. Great. [10:17] And now, here is when I would want to [10:18] move my window to the right by one [10:21] position. And when I move my window to [10:23] the right by one position, I know that [10:24] this trailing element over here is not [10:27] going to be part of my window anymore. [10:29] Right? So, what I can do is just [10:31] subtract it from my current sum. So, my [10:34] current sum is 16. I subtract the [10:35] trailing element of one. That gives me a [10:38] current sum of 15. [10:39] And as I move my window to the right, [10:41] that also means that this element over [10:43] here, this leading element of 25, it's [10:45] going to be now part of my window. So, I [10:48] should add that 25 into my current sum. [10:51] 15 + 25 gives me 40. And that 40 is [10:55] going to be the sum of that next window [10:57] right here. Right? And double-check your [10:59] work here. 4 + 1 + 10 + 25 is indeed [11:03] going to give us 40. [11:05] Great. [11:06] So, at this point, I can continue my max [11:08] value logic. [11:09] I compare the 40 to the 16. Of course, [11:11] the 40 is going to replace it. And I [11:13] continue this algorithm. The key is I'm [11:16] going to subtract my trailing element [11:19] and add my leading element. So, I [11:21] subtract the four from my current sum. [11:24] Gives me 36. And don't forget to add [11:26] your leading element of three. 36 + 3 [11:29] gives me 39. And that would be the sum [11:32] for this next window over here. [11:34] Great. Do your max value logic. 39 is [11:36] not going to replace the 40. So, I [11:39] continue sliding to the right. [11:40] Again, I subtract the one here, but also [11:43] add the five, giving me my next window [11:45] of 43. 43 is bigger than the max right [11:48] now of 40, so I replace it. [11:50] And go ahead and keep sliding your [11:51] window to the right. Here, I need to [11:53] subtract the 10 and add a zero, which [11:55] means that my current sum [11:57] is going to be 33. [11:58] 33 is not bigger than 43, so it stays. [12:01] Go ahead and slide your window one more [12:02] time. I subtract 25 and add 26. [12:06] That gives me a current sum of 34. 34 [12:09] does not replace the 43. At this point, [12:12] I'm done sliding my window all the way [12:13] to the right. So, the final value of my [12:16] maximum sum would be the true maximum of [12:18] any subarray inside of my original [12:20] array. [12:22] Uh so, with that small change, let's go [12:23] ahead and talk about the complexity of [12:25] this new algorithm. [12:27] So, the number of subarrays that we [12:28] consider is really the same. It's still [12:30] going to be n minus k, right? We still [12:32] slid the window uh throughout the nums [12:34] array. So, it's still n minus k. [12:37] What did change was the amount of work [12:39] per subarray. If you think about it, [12:41] what did we actually do? We only did two [12:43] steps per subarray. So, just recall, [12:46] whenever we considered uh some window, [12:49] all we had to do to get to the next [12:50] window to the right was subtract the [12:53] trailing element and add the leading [12:55] element into our current sum. So, the [12:58] amount of work is really just two. What [13:00] we're really saying is we just have a [13:01] constant amount of work uh no matter how [13:04] big the window is, right? Here, our [13:06] window is a size of four, but imagine [13:08] your window was a size of 10. You would [13:10] still only need to subtract a single [13:12] trailing element and add a single [13:15] leading element. So, that's really a [13:17] great optimization here. [13:19] So, let's talk about the total [13:20] complexity of this new and improved [13:21] algorithm. If you want to go nice and [13:22] slow here, you can still say uh that the [13:25] time complexity is going to be the [13:26] number of sub arrays multiplied by the [13:29] amount of work per sub array. Here we do [13:31] n - k * 2, but of course you can [13:33] simplify things. Two is just a constant [13:35] factor, so you can drop it completely. [13:38] And like we said, here we know that n is [13:40] greater than or equal to k, so I can [13:41] simplify this quantity even more. It's [13:43] really just going to be an O of n time [13:45] complexity for this. [13:46] This would be the perfect optimized [13:48] sliding window time complexity. [13:51] Naturally, if you compare this to our [13:52] initial naive solution, our previous [13:54] version was n * k, but our new and [13:56] improved version is just n. [13:58] If you want to talk about the space [13:59] complexity here, when you go ahead and [14:01] code this up, you're not really going to [14:02] use any scaling data structures. You're [14:04] just going to have a handful of [14:05] variables that you're going to do some [14:07] max value logic as well as some addition [14:09] into. So your space complexity here is [14:11] just going to be constant. [14:13] All right. So now that we have a good [14:14] idea about the plan we want to use, it's [14:16] time to code it up. In the next section, [14:18] I'm going to hop into my text editor, we [14:20] can implement the code and run some test [14:21] cases. It's really important that you [14:23] follow along. If you head to the video [14:25] description, you'll find timestamps [14:27] along with links to the coding workspace [14:29] that I'm going to be using. So feel free [14:30] to code along there. Or if you're more [14:32] comfortable, feel free to edit in your [14:34] own text editor. I'll be sure to pull up [14:36] test cases on the screen so you can also [14:38] test your work. I'll be coding in [14:40] Python, but in our workspace, you can [14:41] feel free to switch the language to [14:43] Java, C++, or JavaScript as well. [14:48] Hey programmers, Alvin here. Right now, [14:49] let's go over the Python walk-through [14:51] for this max sub array sum size k [14:53] problem. So definitely make sure you [14:55] watch the approach video first, because [14:56] we're going to learn a new strategy. [14:58] What we want to do is apply the sliding [15:00] window algorithm. [15:02] And so, I'll solve this in two ways. [15:03] I'll solve it with my baseline sliding [15:05] window algorithm, and then I'm going to [15:06] optimize it to get the most optimal time [15:08] complexity here. [15:10] And so, to get going, let's go ahead and [15:12] implement that very first version. So [15:14] what I want to do is uh create some [15:16] variables here. In the long run, what I [15:18] want to do is return the maximal sub [15:20] array sum. So I'm going to create a max [15:22] sum variable here. [15:23] Like we expect, it's really important [15:25] that we default this to a nice value. [15:26] I'm going to set it equal to negative [15:29] infinity. [15:30] Cuz I know that anything I actually find [15:31] is going to replace this value. [15:34] Great. Then from here, I want to start [15:36] looking at my window. So, I'm going to [15:38] create a nice little for loop here. I'll [15:40] say for I in range, and you're going to [15:43] start at the very beginning of your nums [15:44] array. [15:45] And you want to go toward the end, but [15:47] you have to be sure that you don't go [15:48] out of bounds. So, this gets a little [15:50] tricky really to figure out exactly [15:52] where your stopping condition is. You [15:54] want to just look at an example, but [15:56] I know that's going to be up to the [15:58] length [15:59] nums minus K. [16:02] But then also a plus one here. I'll kind [16:04] of explain why that is so we avoid any [16:07] off-by-one errors. So, I'll bring in the [16:08] first example. [16:12] So, let's just quickly check the [16:13] boundary of this loop here. So, it makes [16:16] sense that I'm starting at index zero [16:17] because your first window needs to start [16:19] here. And notice that my K is three. So, [16:21] I want to grab three elements at a time. [16:23] So, the very first iteration is going to [16:25] be right here, which is great. [16:27] Of course, on the other end, I know my [16:28] very last iteration needs to be this [16:32] over here, right? Do you bear in mind [16:34] that the length of this nums array right [16:36] now, there are seven elements. So, here [16:38] I'm doing 7 - 3, right? Cuz K is three. [16:42] 7 - 3 gives me four, right? And then I [16:45] do a plus one to it. So, that gives me [16:47] five. If I count my indices, they go 0, [16:50] 1, 2, 3, 4, and 5. I do bear in mind [16:55] that the range function within Python, [16:58] the second argument is exclusive. So, [17:00] although I'm passing in the index of [17:02] this element over here, it's going to be [17:04] excluded in my range. So, really the [17:06] last iteration starts here at the eight [17:09] and goes all the way through the end, [17:10] giving me my very last window. That's [17:12] why I need to do the plus one over here, [17:14] just to make sure that I end in the [17:16] right scenario. [17:17] Great. [17:18] And so from here, now I'm able to [17:20] iterate through all of my windows and [17:22] I'm sliding them to the right. In the [17:24] naive solution, all you would do is take [17:26] the sum of everything within that [17:27] window. So what I can do is create a [17:30] variable, I'll call it my current [17:32] sum. [17:34] And I'll use the built-in sum function [17:35] in Python. It's really useful here. [17:37] I could say sum, I could pass in just a [17:40] sub array. [17:41] So the sub array that I want to grab is [17:42] going to be from nums. It's going to [17:44] start index I [17:46] and [snorts] go to the next K element. [17:48] So it'll be I [17:50] plus K over here. [17:53] Great. [17:53] And so again, we could do a little spot [17:55] check if you like. Let's say I'm [17:56] somewhere in the middle of this [17:57] algorithm. Let's say that right now [18:00] I is pointing to this element over here, [18:03] right? So it has index two, cuz I go 0 1 [18:07] 2. I know I want to grab these three [18:09] elements, right? So what I'm saying is [18:11] start at index two, which is correct, [18:13] and go all the way up to but not [18:15] including two plus three, cuz again my K [18:18] is three. [18:19] So 2 + 3 is 5. So if I count my indices, [18:21] 0 1 2 3 4 5, right? And the second [18:27] argument into this Python list slice is [18:29] going to be exclusive, so I won't [18:31] include this four, which means I grab [18:33] the one, the -9 and 8. So that works out [18:35] nicely here. [18:37] Now that you have the current sum, go [18:38] ahead and just do your max value logic, [18:40] right? So I'll go ahead and check if my [18:42] current sum [18:43] it's bigger than the max sum, then I [18:45] also replace it, right? Max sum should [18:47] be equal to the current sum. [18:50] Then at the very end, return your max [18:52] sum. Do you bear in mind that I'm only [18:53] returning the maximum after I'm done [18:55] looking at every possible sub array [18:56] here. [18:58] So I'll comment this out and I'll give [18:59] it a test run. This is going to be our [19:01] naive solution. It does give you some [19:03] correct results for the most part, but [19:05] it will time out for some larger test [19:07] cases. [19:09] Great. So let's go ahead and optimize [19:11] this now using what we spoke about in [19:13] the approach video. [19:15] So, I'll go ahead and create my version [19:17] two of this. Which will be a little [19:19] faster. [19:20] So, I know that in this version two, [19:22] what I want to do is have two variables. [19:24] I want the current sum of my window, as [19:26] well as the max sum. So, I'm going to [19:28] create that over here. Set equal to sum. [19:31] I'm going to grab the very first window, [19:33] which would be nums. [19:35] From the very beginning all the way [19:37] through the first K elements. So, if K [19:38] is three, this would grab the sum of the [19:40] first three elements here. [19:43] Great. [19:44] And so, from here, uh what I want to do [19:46] is now go ahead and form the general [19:49] algorithm. Which means I need to iterate [19:51] through everything else. So, I'm going [19:52] to say for I [19:54] in range. So, I'm starting at the very [19:56] first index and go all the way through [19:58] the last index you want to hit, which [19:59] would be the same in the condition from [20:01] before. So, I'm grabbing this. [20:04] This would be my uh very last window. [20:06] So, really because my K is three in this [20:08] particular example, I start grabbing at [20:11] this window. My last window is going to [20:13] be this one. [20:14] And you just need to do the plus one [20:16] here to account for that in Python, cuz [20:18] this argument is going to be exclusive. [20:20] Cool. [20:21] And so, from here, here's where we work [20:23] in that uh fixed number of steps to [20:26] compute the next window, right? So, [20:29] instead of actually calculating the sum [20:30] of everything in between, I want to make [20:32] sure I only do a constant number of [20:34] operations here. In the approach video, [20:35] we said that we would subtract our [20:37] trailing element and add our leading [20:39] element into our current sum. [20:42] So, I know I already considered my [20:44] initial window right here, right? I just [20:48] manually grabbed the sum of the first [20:50] three elements. So, in this particular [20:51] example, my current sum would be 4 + 2 + [20:54] 1, which would give me a seven, right? [20:57] And so, current sum is seven, you will [20:59] want to actually initialize that into [21:02] your max. So, I'll say my max sum is [21:05] going to be my current sum right now. [21:08] It's really important for this like [21:09] optimized version of our sliding window [21:11] algorithm, you will have to treat the [21:13] very first window in a special way, [21:16] right? Your first window is handled with [21:18] this code and all subsequent windows are [21:21] going to be handled by uh this for loop [21:23] here. [21:24] And so, in this for loop, what I want to [21:26] do is now help compute the uh next [21:28] window. So, what I can do is I can take [21:30] my current sum and I want to subtract [21:32] from it the element that is leaving the [21:34] window. So, this is my current window, [21:36] my next window is going to be this guy [21:38] over here, which means that the four [21:39] needs to leave. So, I better subtract [21:41] that four from my current sum. [21:44] So, here I'll say current sum minus [21:46] equal nums at square bracket I, right? [21:50] Cuz again, that would be the start of [21:52] the window here. [21:54] And on the flip side, [21:55] you want to add into it [21:57] the element that's entering the window. [21:59] So, if this is my current window and [22:01] this is going to be my next window over [22:03] here, it would be this -9, right? That [22:06] just entered my window. And you can do [22:09] that by doing I + K here. It makes [22:12] sense, you're just grabbing K elements [22:14] after your current index. There is a lot [22:17] of indexing that we do in an algorithm [22:18] like this, so feel free to pause the [22:19] video and double-check that the math [22:21] works out for yourself here, right? But, [22:24] trust me on this one, this is going to [22:25] work. [22:27] And now that I'm calculating my current [22:29] sum properly, here's where I would do [22:32] the check. [22:33] And now I want to check, all right, if [22:34] this next window, if the current sum is [22:37] greater than the max sum. And if it is, [22:40] then I just do my max value logic. So, [22:42] your max sum equal to the current sum. [22:45] And after you do this for every [22:47] remaining window, just return what's [22:48] ever in the maximum. [22:50] Awesome. So, let's go ahead and test [22:53] this out now. [22:55] So, it looks like I have a little error [22:56] here and a pretty common one at that. [22:58] I'm going to add out of bounds, so I do [23:00] want to check things here. [23:02] Probably have an off-by-one error. [23:04] And if I'm getting my list index out of [23:06] range, that probably either mean toward [23:08] the beginning of my uh nums array or at [23:12] the end of it. And looking at this code [23:13] when I do I + K, that's me looking ahead [23:16] in the list. So, I'm probably looking [23:18] outside of the right edge of my list [23:20] here. So, let's go ahead and think about [23:22] like the last iteration of our code. And [23:24] it might have to do with this plus one I [23:26] have here. [23:27] I probably don't need it. I know that I [23:29] copied this part of the range from this [23:31] previous code over here, but the logic [23:33] is probably a little different, so [23:34] that's probably why it's erroring out. [23:35] And so, I know that this is the scenario [23:38] where my I is pointing to the start of [23:39] the very last window. Yeah, and I can [23:42] already see because here if I do my [23:45] current sum minus equal nums I, means [23:47] I'm going to be subtracting the eight, [23:50] right? And then I'm going to try to add [23:52] the next incoming element. Here I take [23:54] my current position and then I add three [23:55] to it, right? Because K is three. So, if [23:58] my current position's here and I add [23:59] three to it, I go one, two, and three is [24:02] out of bounds, right? Because this is [24:04] really my very, very final [24:06] window, I don't actually need to look [24:08] ahead anymore. [24:10] Right? So, that's why this code is going [24:12] out of bounds. So, in this optimized [24:13] version, you actually don't need the [24:15] plus one here. [24:16] Great. [24:17] So, let's go ahead and test it out now. [24:21] There we have our nice solution. [24:23] The thing I want to really call [24:24] attention to is how we set up this [24:26] optimized version. It really is kind of [24:28] like a two-parter to me. First, you have [24:30] to explicitly handle your initial [24:32] window, right? Here I just went ahead [24:34] and grabbed the immediate sum of the [24:36] first K elements. And then the for loop [24:38] is going to handle all subsequent [24:40] windows. [24:41] And if you do this in a smart way, you [24:43] should do is only a fixed number of [24:45] operations to calculate the next window. [24:48] In particular, here I just did a simple [24:50] subtraction of my trailing element and [24:52] also a simple addition of my leading [24:54] element, right? Because I only have two [24:57] steps for every iteration of the for [24:59] loop, I get that overall O of N run [25:02] time. Here I actually ended up using [25:04] some extra space just for convenience. [25:06] Here when I did the built-in sum [25:08] function call, I'm actually passing in a [25:11] copy of a sub array, which of course [25:12] takes a little bit of space. But it's [25:14] really easy to optimize this away if you [25:16] really cared about getting down from [25:18] like a linear space complexity or O of N [25:20] space complexity here down to a constant [25:22] space complexity. I can show you that [25:23] really quick. It's really nothing fancy. [25:26] You just say your current sum equal to [25:27] zero and you just have to manually [25:28] compute this, right? So you can say for [25:31] I in range [25:34] and start index zero and go through the [25:36] first K elements, so just K over here. [25:39] Nice. And then just take your current [25:41] sum and add into it nums of I. [25:45] So here you wouldn't be using any [25:47] additional space. Let's test it out. [25:49] To be honest, if I was on an interview, [25:51] I'd probably still use uh the built-in [25:53] sum function just cuz it's really [25:54] convenient. And generally, we're okay [25:56] with uh trading off some linear space as [25:58] long as we get the optimal time [26:00] complexity. All right, programmers, [26:02] that's all I got for this one. [26:03] Definitely take some time here and make [26:04] sure you feel comfortable with the [26:06] indexing. A lot of opportunity for [26:07] off-by-one errors, as you can see, the [26:09] one I just made. And don't worry, we're [26:11] going to be able to practice this [26:12] concept further in the upcoming module. [26:16] Hey programmers, Alvin here. Right now, [26:17] let's go over the max sub array product [26:19] size K problem. This is going to be a [26:22] nice build off of our very last problem, [26:24] uh practicing the sliding window [26:25] algorithm. So here we're still given an [26:28] array of some numbers as well as a size [26:30] K. What we want to do is consider uh [26:32] different sub arrays of size K or size [26:35] four here and find the one with the [26:36] maximal product. So for this very first [26:39] sub array, it has a total product of 24. [26:41] Of course, the product is just going to [26:42] be what we get when we multiply all the [26:44] elements together. [26:46] If I look at some other sub array here, [26:48] this one at the very end has a total [26:50] product of -780. [26:52] This one in the middle has a product of [26:54] 270. [26:56] And this would actually be the answer I [26:57] want to return. In other words, you [26:58] should return 270 because it's the [27:01] maximum product we can get of any such [27:03] subarray. [27:05] Great. So, it should be pretty clear [27:06] that this is going to be a small [27:07] variation of the very last problem. So, [27:09] we can practice that sliding window. [27:11] So, like you expect, because I want to [27:12] find the maximum here, just maintain a [27:14] max product variable. So, we'll start by [27:17] talking about the naive sliding window [27:18] strategy just for some nice review. [27:21] So, now that we have my window at the [27:22] very front here, we would need to [27:23] multiply these elements together, right? [27:26] So, their total product is 24. Because [27:28] you have no maximum product so far, that [27:31] will be your current maximum. [27:32] Then you just slide your window to the [27:33] right. You get the product of these four [27:36] elements. You'll get -72. [27:38] That's not going to replace the maximum [27:40] so far. So, you go to the right. [27:42] Here you have a total product of -54. [27:45] Still don't replace it. [27:47] Here you have a total product of 720. [27:50] So, you would replace your max product. [27:53] This algorithm will continue all the way [27:54] through to the end of your array here. [27:57] And of course, 720 would be your [27:58] ultimate answer. [27:59] We already said how this algorithm so [28:01] far has a time complexity of n * k, [28:05] right? It's really the same analysis [28:06] that we did last time. [28:08] Uh the issue with this algorithm so far [28:10] is that factor of k, right? Because [28:12] we're just naively multiplying all of [28:14] the elements within any particular [28:16] window, we'll have to do k operations [28:19] for every window that we look at. [28:21] And so, what I want to do is get rid of [28:23] that k. And here's the optimization. [28:25] Instead of looking at every single [28:27] element within your window, you don't [28:28] want to do that. Instead, just try to [28:30] look at two elements at a time. So, [28:33] here's what I mean. [28:34] We're going to start our algorithm at [28:35] the very front. [28:36] And in addition to our max product [28:38] variable, we're also going to track our [28:40] current product. This is going to be the [28:43] current product of our window so far. [28:46] Because I'm at the very start of my [28:47] algorithm, you just need to process [28:48] those first elements. In other words, [28:50] just go ahead and multiply them [28:51] together. In other words, 1 * 4 * 1 * 6 [28:55] gives me 24. [28:56] I can go ahead and set that 24 as my [28:58] maximum thus far. Now that you want to [29:00] slide your window to the right, what you [29:02] could do is just remove that trailing [29:03] element uh from your current product. [29:06] Here you want to do the opposite [29:07] operation. So, over time I was [29:09] calculating the product, in other words, [29:11] multiplying things together. When I want [29:13] to remove some number from the product, [29:15] I just divide, right? Cuz division is [29:16] the opposite of multiplication. So, if I [29:19] do my 24 / 1, it really keeps my current [29:22] product at 24. [29:24] On the flip side, I have this uh number [29:27] of -3 that's going to enter my product [29:29] within the next window. So, I need to [29:31] multiply by -3. So, I multiply my [29:34] current product of 24 by -3 gives me [29:37] -72. And that would indeed uh be the [29:40] total product of that next window here. [29:42] In other words, 4 * 1 * 6 * -3 is -72. [29:48] -72 is not going to replace my maximum, [29:51] so I can continue sliding my window. [29:53] I need to remove this four uh from my [29:55] current product, which means I should [29:56] divide it, right? So, I divide four into [29:59] my -72. [30:01] That gives me -18. And then also be sure [30:03] to multiply your leading element. So, I [30:06] do 3 * the -18 here. [30:09] Giving me my next window of -54. [30:12] Again, -54 is not going to replace my [30:15] max product. So, I keep sliding. [30:18] I go ahead and divide by one and [30:19] multiply by -5. That means my next [30:22] window has a total product of 270. [30:25] 270 would replace my maximum product, [30:27] cuz of course it's bigger. [30:28] So, my max product right now is 270. [30:31] Keep sliding to the right. In my next [30:33] frame, what I do is divide by six and [30:35] multiply by two, [30:37] giving me 90. 90 is not bigger than my [30:39] max product, so I keep going to the [30:41] right. [30:42] Here I need to divide by -3 and multiply [30:45] by 26. [30:46] And this final window has a total [30:48] product of -780. Of course, that's also [30:50] not going to replace my max product. Now [30:53] that I'm done sliding my window all the [30:54] way through the right, the final value I [30:56] have inside of my max product would be [30:58] my final answer. So, the answer here we [31:00] should return is 270. [31:02] Like we said previously, this is our [31:04] optimized sliding window strategy. The [31:06] time complexity for this is just O of N, [31:09] right? When we considered uh finding the [31:11] next product that we have to look at, we [31:13] only did a constant number of [31:15] operations, right? What we said was we [31:17] just divide by our trailing element and [31:19] multiply by our leading element. That [31:21] would be true no matter the size of our [31:24] window, right? Here K is 4, but even if [31:26] K was 100, you would still only need to [31:28] divide by one thing and multiply by [31:30] another thing. [31:32] Time complexity here is O of N. Space [31:34] complexity is also going to be O of 1 [31:35] just like last time. [31:37] Right. So, what I want you to do is try [31:38] to code up this one on your own. It's [31:40] going to be very similar to our last [31:41] problem. It's good practice for getting [31:43] this sliding window algorithm down pat. [31:46] If you get stuck, I'll see you in the [31:47] walk-through video. [31:50] Hey programmers, Alvin here. Right now, [31:52] let's go over the Python walk-through [31:53] for this max subarray product size K [31:55] problem. So, this is just going to be a [31:57] small variation of our last problem, uh [31:59] giving us another chance to practice the [32:01] optimized sliding window algorithm. [32:03] So, I'll jump right in. I'm going to go [32:04] immediately to the optimized version. [32:06] Going to create my current product [32:08] variable. [32:09] Cuz I know the first step is to just [32:11] process the first K elements, right? [32:13] Let's get that first window. [32:15] So, I'm going to iterate for we'll say I [32:17] in range. [32:19] You know, go from zero just to the first [32:21] K. [32:23] And what I want to do is multiply into [32:25] the product [32:27] multiply this current element. So, nums [32:30] at I. [32:31] Great. So, now that I have the product [32:33] of the first window, I can set that as [32:36] the max so far. [32:40] Nice. [32:41] I'll bring in an example here. [32:43] Just so we can talk about it a bit. [32:46] So, we already handled this initial [32:48] window. Now, I need some other loop [32:49] that's going to slide this window all [32:51] the way to the right. [32:52] So, I could consider every sub-array [32:54] here. [32:55] So, I'm going to start still at index [32:57] zero as I iterate here. This time I want [32:59] to stop around length of nums minus K. [33:04] This has the effect of stopping uh [33:06] roughly K elements from the end of the [33:08] list, right? [33:10] Like we said in the approach video, the [33:11] important thing is that we do a constant [33:13] number of steps as we slide our window, [33:15] right? So, right now my window's here. [33:17] If I want to go to the next window, I [33:19] need to remove the four from my product, [33:22] but also incorporate -9 into my product. [33:25] And I need to [33:28] use the appropriate operations for that, [33:30] divide out that trailing element of [33:32] four. So, I could say divide equals [33:35] nums at index I. [33:39] On the flip side, I want to multiply in [33:42] multiply in [33:44] nums at I plus K. [33:47] Nice. So, doing a quick check here, if I [33:49] is zero, that means I would remove four [33:51] from my product. That's good. [33:53] And if I is still zero, and I do K is [33:56] three, that means I'm indexing at three. [33:58] So, it's zero, one, two, three. I would [34:01] be multiplying in my -9, which is also [34:03] good to get my next window. From here, [34:05] you just do your classic max value [34:07] logic. So, check if your current is [34:08] bigger than your max product. And if it [34:10] is, you can replace it. So, [34:12] can say [34:13] max product equals current product. [34:16] Nice. [34:17] Then after you're done sliding your [34:19] window, just return the maximum. [34:23] This will be our optimized version. [34:24] Really, really similar to our last [34:26] problem. Just wanted to give you another [34:27] look at this algorithm. [34:29] Great. [34:30] Another way you could write this is [34:31] maybe using the built-in max function. [34:34] So, we could say max product equals [34:36] just call max, pass in those two [34:38] variables. [34:39] It would be the same way to write this, [34:40] just in a one-liner. [34:44] Really, the important thing here is that [34:45] you go for that O of N run time. Right? [34:47] I have K iterations in this for loop, [34:49] and then the rest of that uh input array [34:51] is going to be iterated in this for loop [34:53] here, for which I only do a constant [34:55] number of operations each time. Notice [34:57] that I did not nest any loops here. [35:00] Hey programmers, Alvin here. Right now, [35:02] I just want to give us a quick summary [35:03] of the algorithm that we've been [35:04] implementing lately. So, for the last [35:06] two problems, we've been exploring the [35:08] sliding window strategy. In particular, [35:10] we've been looking at the sliding window [35:12] with a fixed size K. [35:14] And so, naturally, this is good for [35:16] considering sub-arrays or sub-strings of [35:19] one size. The one size being that K [35:21] argument. And like I'm saying here, not [35:24] only is this strategy good for [35:25] considering sub-arrays within a larger [35:27] array, but it's also great for [35:28] considering sub-strings within a larger [35:30] string. And we'll see that later on. It [35:33] really doesn't change in any particular [35:34] way. [35:36] And so, let's summarize the steps that [35:37] we've been using so far. And I think for [35:39] the most part, this is going to be a [35:40] good recipe whenever you're applying the [35:42] sliding window with a fixed size [35:44] strategy. [35:45] And so, your first step is going to be [35:47] to process the first K elements into [35:49] some collection. What you've noticed [35:51] thus far is that this process actually [35:53] happens separately. Usually, we have an [35:55] initial uh loop that's going to process [35:58] the first K elements to get our initial [36:00] window rolling. [36:03] And then from there, what you want to do [36:04] is move the window to the right using [36:06] some other loop. And this is the really [36:08] key part. In the long run, you want to [36:10] go for a roughly linear uh time [36:12] complexity. And so, you want to keep the [36:14] number of steps as you move the window, [36:16] you want to keep that constant. [36:18] So, your first move is going to be to [36:19] remove the trailing element from the [36:21] collection, right? In other words, the [36:23] thing that is leaving the window, you [36:25] need to remove it from your collection, [36:27] whether that's your a product or your [36:28] sum or some other data structure like [36:31] we'll see later on. [36:32] In addition to that, because you're [36:33] moving your window to the right, that [36:35] means some leading element needs to be [36:36] added to the collection. [36:40] Generally, these remove and add [36:41] operations should be opposites, right? [36:43] So, in the case of calculating a total [36:45] sum, your remove is going to be [36:47] subtraction and your add is going to be [36:49] addition. In the case of taking some [36:51] large product, your remove is going to [36:52] be division and your add is going to be [36:54] multiplication. [36:56] And do try to visualize things over [36:58] here, right? So, when I have the window [37:00] like we've been exploring in the last [37:01] few problems, your trailing element is [37:04] really the last thing that's about to [37:05] leave your window and then your leading [37:08] element is about to enter your window. [37:10] So, of course I'm going to slide this [37:11] orange window to the right. [37:14] So, now that you've established your new [37:15] window, you just do the business logic [37:17] and that really depends on the context [37:19] of the problem. So, thus far we've done [37:21] things like taking the max. Obviously, [37:23] this wouldn't change much if you took [37:24] the minimum and of course I'm going to [37:26] show you a lot more variations as we [37:28] move through the course. But the great [37:29] thing is with the sliding window of [37:31] fixed size strategy, this is my general [37:33] recipe and it works pretty great. After [37:36] you do the business logic, you need to [37:38] go back to step number two, keep moving [37:40] your window to the right and you just do [37:41] steps two and three again and again [37:43] until you've processed uh your entire [37:46] array. [37:49] All right, so that's our little summary [37:50] of the sliding window with fixed size K [37:52] strategy. We'll go ahead and practice [37:54] some more problems right now and of [37:55] course we're going to increase the [37:56] difficulty, that way you're ready for [37:58] your interviews. [38:02] Hey programmers, Alvin here. Right now I [38:04] want to go over the approach we can use [38:05] for the subarray target sum size K [38:07] problem. [38:09] In this problem, we're given three [38:10] arguments. Our first argument is just [38:12] going to be an array of some numbers. [38:14] Our second argument is going to be a [38:16] target sum. [38:18] And our third argument is going to be [38:19] the size K. [38:21] Here we're considering uh sub arrays of [38:23] size three that sum up to seven. What we [38:26] want to do is count those. So, how many [38:28] sub arrays of size three sum up to [38:30] seven? [38:31] The result here should be five. Because [38:33] there are five different sub arrays that [38:35] meet that criteria. Here's the first sub [38:37] array. Of course, 2 + 3 + 2 is indeed [38:39] seven and it's three elements, so that's [38:41] good. [38:42] Here's number two. [38:44] Number three. [38:46] Number four. [38:47] And then your fifth and final. [38:49] So, really this is going to be a [38:50] counting problem for us. But of course, [38:52] we're going to utilize that sliding [38:54] window strategy. [38:56] We know that this problem is a good fit [38:57] for a sliding window uh because of [38:59] course, we're considering sub arrays of [39:01] some fixed size. [39:03] So, what I want to do to get going is [39:04] just process the first K elements [39:07] depending on my window size. [39:09] So, looking at my uh very first window, [39:11] here it is. I want to just find the sum [39:13] of them. Cuz of course, I'm looking for [39:15] something that matches the target sum in [39:17] the long run. [39:18] So, 2 + 3 + 2 gives me seven. We're just [39:22] going to start by implementing the [39:23] optimal solution cuz by now, you should [39:25] be familiar with how it's going to go. [39:28] So, in addition to the sum of our [39:29] current window, what I also want to do [39:31] is keep track of the global count, [39:33] right? That's going to be the answer I [39:35] eventually return. [39:36] Right now, my sum is exactly the target, [39:39] so I should count it. So, right now my [39:41] count is one. [39:43] And I'm ready to move my window. So, I'm [39:45] ready to slide it to the right. Like we [39:46] expect, what you want to do is remove [39:49] your trailing element from your sum and [39:51] then add your leading element into the [39:54] sum. [39:55] So, I do a minus two and a plus two, [39:57] which really doesn't have an effect on [39:58] changing the sum, but it is going to be [40:01] considering the next window. [40:03] It's still the case that my sum matches [40:05] the target, so I should also increment [40:07] my count. [40:09] And I continue. I do a minus three and [40:11] also a plus three. So, my sum for this [40:13] window is still seven. So, I should [40:15] count it. [40:16] Keep moving to the right. Here I do a [40:18] minus two and plus one. [40:21] That gives me a current sum of six. Six [40:23] is not equal to the target of seven, so [40:25] I don't increment my counter. [40:27] Keep this pattern going. I'm going to [40:28] subtract my trailing element of two and [40:30] add my leading element of three. [40:32] Now my sum is seven. Because seven [40:34] matches my target, I increment my count. [40:37] And we're going to continue this logic, [40:39] updating our current sum and comparing [40:41] it against our target of seven [40:44] until we find any matches. [40:47] You're going to reach your next match [40:49] right about here. [40:51] Here you have a sum of seven. It matches [40:52] your target of seven, so you should [40:53] increment your count one more time. [40:57] And once you hit the end of your array, [40:59] you're done considering all possible sub [41:01] arrays of size three. You just go ahead [41:03] and return the counts over here. [41:07] So by now you should anticipate what the [41:08] complexity of this is. This algorithm [41:10] just has an O of N run time, where N is [41:12] going to be the length of the nums [41:14] array. [41:15] Space here is going to be constant. It's [41:17] really the same analysis that we did for [41:19] the previous two problems. So what I [41:21] want you to do is try to code this one [41:22] up on your own. If you get stuck, you [41:24] can catch me in the walk through video. [41:28] Hey programmers, Alvin here. Right now [41:29] let's go over the Python walk through [41:31] for the sub array target sum size K [41:33] problem. [41:34] So of course we want to continue the [41:36] theme as of late. We want to solve this [41:37] one using our sliding window of a fixed [41:39] size algorithm. [41:41] And so to get going, I'm going to [41:43] process my first K elements. Here we [41:45] still want to find the sum of our sub [41:47] arrays, but this time we want to count [41:48] them, so [41:50] I'll still have my, we'll say, current [41:52] sum. [41:53] Initialize it to zero. [41:54] I just want to process the first K [41:56] elements. [41:57] So I say four I in range, go from zero [42:00] just up to K. [42:02] And I want to add the element, so [42:04] current sum plus equals [42:06] nums [42:07] at index I. [42:10] Now along the way I want some count [42:11] variable which I'm going to return at [42:12] the very end. [42:13] And do bear in mind that because you've [42:15] already processed the first window, you [42:18] should check the sum of that window and [42:20] see if it matches the target. So here, I [42:22] might just use a Python ternary, so I [42:24] can check, all right. [42:26] I'll set it I'll set the count equal to [42:28] one [42:29] if the current sum [42:31] is equal to the target. Otherwise, if [42:34] it's not equal to the target, then [42:35] initialize it to zero. [42:37] Cool. [42:38] Uh for our sliding window with a fixed [42:41] size the initial window is kind of [42:43] processed separately, so it's important [42:45] to make sure you still count it if [42:47] necessary. [42:48] And then this code now over here with [42:50] the for loop is going to handle all [42:52] other windows, right? So I'll say for I [42:54] in range, go from zero, go up to length [42:58] of nums [42:59] minus K. So this has the effect of [43:01] stopping K elements from the right edge [43:04] of my list here. [43:05] And because I'm dealing with some logic, [43:07] it's straightforward, just do current [43:08] sum, subtract out your trailing element, [43:11] so nums [43:13] I [43:14] and then add in your leading element [43:17] which is at index I plus K. [43:20] Now you need to work in the specific [43:21] logic for this problem, which is just [43:23] checking your current sum, right? Check [43:25] if the sum of this window matches the [43:27] target, and if it does, then just count [43:30] it. So count plus equals one. [43:32] That's all there is to it. Should be [43:34] very comfortable with seeing this [43:35] pattern again. [43:37] Great, so looks like our code is [43:38] passing. Something I want to emphasize [43:40] here is I think the most common mistake [43:41] for [43:42] uh some of your sliding window of fixed [43:44] size problems is to not correctly uh [43:47] consider the very first window because I [43:49] handle it specially using this for loop, [43:51] be sure to check if that initial window [43:54] sum is already equal to the target, then [43:56] you want to initialize your count to [43:57] one, otherwise you set it equal to zero. [44:00] Cool. Really uh the first window is [44:02] handled specially in this code, and all [44:04] subsequent windows are handled in this [44:06] code. [44:07] Hey programmers, I wanted to take a [44:09] quick break to tell you about my [44:10] complete data structures and algorithms [44:12] course at structy.net. [44:15] If you enjoy my teaching style, then I [44:16] think you'll really love my full course. [44:19] The sliding window material we've [44:20] already been working through is actually [44:22] taken straight from my course at [44:24] structy.net. There I'll teach you [44:26] everything you need to know to pass your [44:28] DSA interviews. There I'll cover sliding [44:31] window, trees, graphs, dynamic [44:33] programming, and much more. [44:35] The best part is I'll be there to [44:37] explain each problem using the same [44:39] clear animations and code walkthroughs [44:41] that you're used to. That's structy.net. [44:44] I'll leave a link in the video [44:45] description if you're interested. And [44:47] now, let's get back into our sliding [44:48] window course. [44:53] Hey programmers, Alvin here. Right now, [44:54] let's go over the approach we can use [44:55] for this has substring anagram problem. [44:58] So, in this problem we're given two [44:59] strings. Here I have a string input [45:01] greyhounds. I'm also given the target [45:03] anagram of HOI. H O Y. [45:06] What I want to do is return a boolean [45:07] true or false indicating whether or not [45:09] the anagram is found somewhere as a [45:11] substring in the larger string here. [45:14] So, if I look for the characters H O Y, [45:16] recall that an anagram can have its [45:18] characters rearranged, right? In this [45:19] particular example, it is actually the [45:21] case that I could find an anagram of H O [45:23] Y as a substring in greyhound. [45:25] It would be right here, right? Y H O. [45:28] Recalling that an anagram can have its [45:29] characters appearing in any order. [45:31] So, for this particular input, you [45:32] should return true. [45:35] Let's take a look at another example. [45:36] Let's say you're given this string. [45:38] You're still given the target anagram of [45:40] H O Y. [45:42] For this case, you should return false [45:43] cuz there is no substring that contains [45:45] an anagram of H O Y. [45:48] So, if you can't find the substring [45:49] anagram, you just return false. [45:52] So, let's talk about the approach here. [45:54] For this particular problem, what we [45:55] want to do is consider substrings. [45:58] Something important about substrings is [46:00] uh they're going to be a consecutive [46:02] sequence of characters within a larger [46:03] string. [46:04] A substring is just like a subarray. [46:06] Instead of dealing with an array, you're [46:07] dealing with a string. [46:09] We're also checking if the anagram [46:10] exists anywhere in the string. Here my [46:13] anagram of h o y has three characters, [46:15] so I'm looking at substrings of length [46:17] three. [46:19] Based on what we've been practicing [46:20] recently, we know that we can easily get [46:22] all substrings of length three by just [46:24] sliding some window throughout my [46:26] string. [46:27] So, we're going to solve this using a [46:28] sliding window strategy. It's going to [46:30] be a little different though. Notice [46:31] that this one doesn't deal with any [46:32] numbers. [46:33] All right, so we know we need to slide a [46:34] window to consider different substrings, [46:36] but how can we come up uh with checking [46:38] if we actually have an anagram? [46:41] Well, the key is going to be to use a [46:42] set. So, recall that your set data [46:44] structure is something that has constant [46:46] time uh insertion of elements, and also [46:49] constant time removal, and constant time [46:51] lookup. And so, why is using a set a [46:53] good idea in this problem? Well, a set [46:54] has some uh very important [46:56] characteristics. For one, the items in a [46:58] set are unordered. And that's actually a [47:01] good fit because an anagram could have [47:03] its characters appearing in any order. [47:06] Besides that, I also know that items in [47:08] a set are necessarily going to be [47:10] unique, which is actually an assumption [47:12] that they give us in the problem. They [47:13] tell us that the characters within the [47:14] string, as well as the characters in the [47:16] anagram, are all going to be unique. So, [47:18] those two characteristics uh do fit [47:20] nicely with the usage of a set. All [47:23] right, so how would this algorithm flow? [47:24] For the most part, it's going to be our [47:26] uh sliding window algorithm of a fixed [47:28] size, but we're just going to use a set [47:30] throughout. [47:32] So, we're going to start with an empty [47:33] set. [47:33] >> [gasps] [47:34] >> And like we said previously, uh we want [47:35] the first step of the sliding window of [47:38] a fixed size algorithm uh to just [47:40] initialize and process the first k [47:43] elements. In this particular example, [47:44] because my anagram has a length of [47:47] three, really my k or my window size is [47:49] just three characters. [47:51] So, if I just grab the first three [47:53] characters in my first window, I I just [47:55] add them all uh into my set. So, each [47:58] character is one item of the set. [48:00] Great. [48:01] At this point, I can just check [48:03] are the characters of my anagram, do [48:05] they exist within my set? Right now, [48:08] that's not the case. So, this is not an [48:09] anagram so far. So, I need to keep [48:11] going. [48:12] Like we expect, if you want to do this [48:14] efficiently, what you want to do is try [48:16] to keep your operations as constant as [48:19] possible as you move your window to the [48:21] right. [48:22] So, what I'm going to do is I'm just [48:23] going to remove my trailing character, [48:25] right? So, I'm going to remove it from [48:27] my set. And I'm also going to insert my [48:30] leading character. Going to add that [48:31] into the set. [48:33] So, I'll go ahead and remove the G. [48:35] But then also add the Y. [48:37] So, now it's as if I'm considering this [48:39] next substring, R E Y. And again, I [48:42] check, is my anagram, H O Y, do those [48:45] characters exist inside of my set? And [48:48] they don't, so I keep going. [48:50] I need to progress my window a little [48:51] bit to the right. So, I remove the R and [48:53] add the H. [48:56] That brings me to my next window. [48:58] Again, I check, are the characters of my [49:01] anagram, are they present inside of the [49:02] set? They're not, so I keep going. [49:05] I remove the E and add the O. [49:08] Like so. And at this point, I'm [49:10] considering the substring Y H O. And now [49:13] I check, does my anagram match the [49:14] characters in my set? That is actually [49:17] the case. So, I know I just found a [49:19] substring that contains the anagram. So, [49:22] I should just ultimately return true. [49:24] Obviously, if you uh need to return [49:26] false, then you're just going to iterate [49:27] your sliding window all the way to the [49:30] right. And if you never find a match, [49:32] then you're just going to return false. [49:33] Some very classic Boolean logic there. [49:36] So, let's discuss the complexity of this [49:37] one. [49:38] So, if you say that N is the length of [49:40] my string [49:41] and K is the length of the anagram I'm [49:43] looking for, then the time complexity [49:45] here is going to be O of N times K. [49:49] And so, where does this come from? If [49:50] for the sake of sliding the window to [49:51] the right, we know we're keeping the [49:52] operations relatively efficient by just [49:55] removing a character and also adding a [49:57] character on every iteration as we slide [50:00] to the right. [50:01] So, you're probably wondering where does [50:02] the K come from? What we have to [50:04] understand is the K comes from the check [50:06] of checking if our original anagram if [50:09] it matches the characters of our current [50:11] set. To do that check, you're just going [50:13] to really just iterate through the [50:14] characters and make sure that each one [50:16] exists. And of course, that will happen [50:18] in K time cuz there are K characters to [50:20] verify inside of the set. In a similar [50:23] way, the space complexity is going to be [50:24] O of K. Now, really the space complexity [50:26] is going to be the size of the window [50:28] cuz we have that many characters inside [50:30] of our set. This is actually a nice [50:32] efficient solution for this one. I do [50:34] note that the complexity for this is a [50:36] little different from the previous [50:37] problems that we just did in the sliding [50:39] window module. Uh mainly, we have a [50:41] factor of K within the time and space [50:43] complexity. So, for I think the last [50:45] three problems, we had a time complexity [50:46] of O of N and a space complexity that [50:48] was constant. Here, it's a little [50:50] different just based on the constraints [50:52] in the problem. Like you expect, time [50:54] and space complexity can differ from [50:55] problem to problem even when it comes to [50:58] the same topic. And that feels okay [51:00] because this problem is definitely a [51:01] step up from the previous problems that [51:03] just dealt with sums and products [51:05] previously. Although, they still use the [51:07] sliding window algorithm. [51:12] Hey programmers, Alvin here. Right now, [51:13] let's go over the Python walk-through [51:14] for this has substring anagram problem. [51:17] So, like we said in the approach video, [51:18] we're going to solve this one using our [51:19] sliding window with a fixed-sized [51:21] algorithm. [51:22] What we're going to do is create a set [51:25] here to contain the characters. That [51:26] way, we can check if we have a matching [51:28] anagram here. [51:29] So, I'll create a set. [51:30] And I do want to initialize the set with [51:33] the characters of the very first uh [51:35] window. [51:36] I know that the window size is really [51:38] just going to be the length of the [51:39] anagram. So, for this particular [51:40] example, my anagram is H-O-Y. That means [51:42] I want to check for a sliding window [51:44] with a the of three here. [51:46] So, what I'll do is I'll just grab the [51:47] first three characters or the first K [51:50] characters, so to speak. [51:52] So, I'll say S [51:53] and I'll go from index zero [51:55] up to the length of the anagram. So, [51:57] length of anagram. [51:59] And Python syntax, I could actually drop [52:01] the zero like so. [52:02] If you want, you can maybe even declare [52:04] like a K variable for this. It'll look [52:07] more similar to code we've written [52:08] previously. [52:10] And then, that'll just look like this. [52:13] So, this is me processing my very first [52:16] window. [52:17] Right? And I'll call that my window set. [52:21] Nice. [52:22] So, now that I have a set containing [52:24] these three characters, what I want to [52:26] do is check if that first window [52:29] actually is a match. So, be sure to do [52:31] that. It's very common to forget to do [52:33] this for the very first window [52:35] in your sliding window algorithm. So, [52:37] I'm just going to check if my window set [52:39] is equal to the set of the original [52:41] characters of anagram. So, I'll just [52:44] create [52:46] another [52:48] set here. I'll call it my anagram set. [52:51] Set. This will be the set of the [52:53] characters of the original anagram. [52:56] Nice. [52:57] And so, what I'll do is just check if [52:58] they match. [53:00] Python has some really great syntax for [53:01] this. All you need to do is check if [53:03] they are double equals. You're going to [53:05] check if the items in the two sets are [53:07] the same, right? In other words, are [53:08] these two sets totally equal? [53:10] Great. So, if that's the case, then I [53:12] can return true cuz I just found a [53:13] match. [53:14] Otherwise, I don't need to check the [53:16] other windows by sliding to the right. [53:18] So, I'm going to set up a for loop. I'll [53:19] say for I in range [53:22] go from the very beginning all the way [53:24] up to but not including my length of S [53:29] minus [53:30] the length of the anagram, which I have [53:32] stored in this like K variable. So, I'll [53:33] use it over here. [53:35] Just say K. The stopping condition here [53:37] is very similar to what we've written in [53:38] our last few problems. [53:40] And so here, what I'll do is the very [53:42] classic sliding window logic. [53:45] So I'm going to remove from my set I'll [53:47] say window set dot remove. I'm going to [53:49] remove my trailing character which would [53:52] be [53:53] S at index I. [53:55] Right? So on the very first iteration [53:57] when I is zero we're going to remove the [53:58] G. [54:00] Then what I need to do is add the Y [54:02] here. [54:03] So remove S of I. [54:05] And then on the other hand you want to [54:07] add [54:08] S at I [54:10] plus K. [54:11] Right? Cuz if my I is zero then if I do [54:13] zero plus three I get one, two [54:16] and then three is the Y right there. [54:18] Cool. That'll bring me to my next window [54:20] which I should now check. [54:22] So I can just check if this window [54:24] set is equal to the anagram set. [54:27] If they match then return true. [54:31] Always having an early return true here. [54:33] And only after I'm done with the for [54:34] loop if I never return true then I never [54:36] found a matching window. So then I can [54:38] ultimately return false here. [54:41] Before we give this a run don't forget [54:42] to return [54:44] the true value here. [54:46] Let's test it out. [54:48] There we have our solution for this one. [54:51] Like we say in the approach video if you [54:52] say that N is the length of the string [54:54] and then K is the length of the anagram [54:56] this would have an overall time [54:57] complexity of N times K. It's pretty [54:59] obvious that the N exists like right [55:01] about here cuz we're iterating through [55:04] roughly the length of our string. The K [55:06] comes from this check over here. [55:08] Although it's a simple a double equals [55:10] in Python under the hood this would [55:12] actually have to iterate uh between one [55:15] of our sets right and check if every [55:17] member of that set is within the other. [55:19] Right? So this is really your K [55:21] operation inside of your N loop. So [55:23] that's why you have a total time [55:24] complexity of N times K. [55:27] Right? Space complexity here is just [55:28] going to be K uh based on the size of [55:31] the sets you create. So mainly your [55:33] window set and also your anagram set. [55:35] They're going to have uh the number of [55:37] characters that is in the original [55:39] anagram here. [55:43] Hey programmers, Alvin here. Right now, [55:45] I want to go over the approach we can [55:46] use for this count substring anagrams [55:48] problem. [55:49] So, in this problem, we're going to be [55:50] given a string S in input. We're also [55:52] going to be given another string [55:54] representing an anagram. [55:56] What I want to do is count the number of [55:58] times that the anagram appears inside of [56:00] the string. Of course, like always, an [56:03] anagram is a string where we can [56:04] rearrange the order of the characters. [56:07] So, if I wanted to actually step through [56:08] this particular example, my anagram is [56:10] ATT, and I can actually find that [56:12] exactly in the string. So, that gives me [56:14] a count of one. [56:15] I can also find occurrences where uh the [56:18] anagram is rearranged, right? So, here I [56:20] have TTA. [56:22] Finally, at the end, I have TAT. That [56:24] would give me a total count of three [56:26] substrings that match with the given [56:28] anagram. So, you just want to return the [56:30] number three here. [56:32] So, this problem seems pretty typical of [56:34] what we've been studying lately, [56:35] especially when compared to the previous [56:37] problem. There is something important we [56:39] do want to note in this particular input [56:41] though. Uh we are allowed to have [56:43] duplicate characters in the input. And [56:45] this contrasts with the previous problem [56:47] where we were guaranteed only unique [56:49] characters. It's pretty plain to see in [56:51] my input string here, A appears multiple [56:53] times, and even the T appears multiple [56:55] times. [56:57] And so, let's say we maybe started to [56:59] attack this similar to our last problem [57:01] using a set. So, we know in the long run [57:03] we're going to use, you know, a sliding [57:04] window strategy. And if you had your [57:06] initial window here, you would convert [57:08] the characters into members of a set. [57:11] So, the corresponding set for your [57:12] window would look like this. Just like [57:14] our last problem, nothing fancy. [57:16] But then, if you actually move this [57:18] window to the right one unit, you would [57:20] end up with this. And you could [57:22] immediately spot the issue here. My [57:24] window has a size of three, and it [57:26] contains ATT. If I look at the [57:28] corresponding set I would have created [57:29] here, it only contains a single A and a [57:32] single T. That's really just a [57:34] constraint of sets, right? In a set, the [57:37] elements of a set are necessarily [57:38] unique. You can't have duplicate [57:40] elements in a set. And so this lack of [57:42] correspondence is going to cause an [57:44] issue for us, right? My set only [57:46] contains two characters, uh but the [57:48] window I'm looking at has three [57:50] characters. And so that's why you won't [57:52] be able to use a set for this one. You [57:54] do need to adjust this logic a little [57:55] bit. [57:56] What you can do to solve this one is [57:58] just modify the logic [57:59] and use a map. Like you already know, [58:02] sets and maps are both hash data [58:03] structures, so they give us a constant [58:05] time look up and access. However, a map [58:08] gives you a key-value pairing. [58:10] And so what will your key and your value [58:12] be in this particular problem? Well, [58:14] your key is just going to correspond to [58:15] a character of your window. And the [58:18] corresponding value is just going to be [58:19] the counts of that character. [58:21] Because a character can be duplicate and [58:23] appear multiple times in our window, [58:25] we're going to use a count to represent [58:27] that information. [58:28] So let's step through our sliding window [58:30] algorithm, but this time using the map [58:33] here. So we're going to start at the [58:34] very beginning, and for the most part [58:36] this is going to feel like a pretty [58:37] classic sliding window of a fixed-size [58:39] algorithm, just adjusting for our map [58:42] logic, right? [58:43] And so when I create my initial window, [58:45] of course I need to consume these first [58:46] three characters, and all that means is [58:49] I uh put them inside of my map here and [58:51] give them the appropriate counts, right? [58:53] So G appears once, A appears once, and T [58:56] appears once. What you can also do is [58:58] generate a similar map for your uh input [59:01] anagram. So my input anagram has one A [59:03] and two T's. That's going to be useful [59:05] when you actually compare them during [59:06] your algorithm. [59:08] And because in the long run I'm [59:09] interested in the counts, right? I want [59:10] to find the number of substrings uh that [59:12] matches the anagram, I'm going to [59:14] initialize some count to zero. [59:16] If I double-check the initial window I [59:18] have right now, it doesn't match the [59:20] anagram. So I don't count it, that's why [59:22] my count begins at zero. And now I can [59:25] enter the general algorithm. So I'm [59:27] going to have my trailing element here, [59:28] which is the G. I also have my leading [59:30] element, which is the next T over here. [59:33] Like you expect, you want to just remove [59:35] your trailing element. So, I've removed [59:36] the G from my map, which means I reduce [59:39] its count to zero. [59:41] At the same time, I need to add my [59:42] leading element in, so I need to add an [59:44] additional T. So, the count of T is now [59:47] two. [59:48] So, now the map actually represents the [59:50] next window over here. [59:52] At this point, I just want to note [59:53] something important that might factor [59:55] into the code that you write for this. [59:57] So, I just decremented the G from a one [60:00] down to a zero. That essentially means [60:02] that if G is zero, that there are no G's [60:04] in my current window. Right? So, I can [60:07] really ignore the G completely. Maybe [60:09] you can remove it from your window map. [60:12] And if you did that, then you would have [60:13] a perfect equality uh between your [60:16] window map, as well as the map of your [60:18] anagram. So, what I'm saying is you [60:20] could compare the window map to the [60:22] anagram map, and you see that they're [60:23] equal. And so, you could increment your [60:25] count by one. [60:27] Cool. So, let's continue the algorithm. [60:29] I need to uh remove my trailing [60:31] character of A, and also add in my [60:33] leading character of A, which has an [60:35] effect of not actually changing the map. [60:38] But, it does bring me to that next [60:39] window. Now that I'm at the next window, [60:41] I should compare my two maps, and [60:43] they're equal, so I increment my count [60:45] to two. [60:46] This point, I slide my window again, [60:48] being sure to update the map [60:49] appropriately. Here, I don't have a [60:51] match between the two maps, so I just [60:53] continue. [60:54] Still no match. [60:56] Still no match. And finally over here, I [60:59] do have a match. That brings my total [61:01] count to three. [61:03] And that's all there is to it. This [61:04] feels very similar to our previous [61:06] sliding window of fixed size algorithms, [61:08] just adjusting it with this uh count [61:10] hash map logic. [61:12] So, if we say that N is the length of [61:13] our string, and K is the length of our [61:15] anagram, let's talk about the complexity [61:17] of this one. [61:18] Similar to last problem, the complexity [61:21] for the time is going to be n * k. The n [61:24] comes from the fact that we have to [61:25] slide this window all the way through [61:28] our input string. So, that's where the n [61:30] comes into play. Where does the k come [61:32] from? Well, the k comes from the fact [61:34] that you have to actually compare your [61:36] two maps. You know that the map in the [61:39] worst case is going to have the same [61:41] size as the window, right? So, on every [61:44] iteration or every time you slide the [61:45] window, you also need to compare the [61:47] contents of your map. The sliding part [61:50] is the n, and the comparison of the maps [61:52] is the k. So, that's why your total time [61:54] complexity is n * k. [61:56] In a similar way, the space complexity [61:58] is just k, coming from the space [62:00] consumed by the map you create. In the [62:02] worst case, if you had all unique [62:04] characters in your window, you would [62:07] have k different keys in that map. [62:10] All right, programmers. What I want you [62:12] to do is give this code a shot on your [62:13] own. There is some tricky logic you [62:15] might need to account for when it comes [62:16] to handling the map. So, if you get [62:18] stuck, you can find me in the [62:19] walk-through video. [62:20] Hey, programmers. Alvin here. Right now, [62:22] I want to go over the Python [62:23] walk-through for this count substring [62:25] anagrams problem. [62:27] So, uh to solve this one, we do want to [62:28] use a bit of a counter hash. And to do [62:31] that really easily in Python, you could [62:32] just use the built-in [62:33] collections.Counter, right? So, what [62:35] I'll go ahead and do is just from [62:38] collections [62:40] import [62:41] counter. [62:42] And what I want to do is I'm going to [62:44] convert just the anagram into a counter [62:48] of its characters. So, that's really [62:49] straightforward. I'll call this my maybe [62:51] just anagram counter. [62:54] I'll just pass in the entire anagram. [62:57] And beyond that, what I want to do is [62:59] establish the counter that's going to [63:01] contain my window. And I'm going to [63:03] initialize here. I'm going to say my [63:05] window counter. [63:08] And do bear in mind that these counter [63:10] objects, they're going to represent the [63:11] character counts of those given strings, [63:13] right? Just like we saw in the approach. [63:15] When When my initial window, I do want [63:17] to create a counter, but I just want to [63:18] grab uh the first window from my input [63:22] string S. [63:23] So, I'm going to do a little slice here. [63:24] I'm going to say S and start at the [63:26] beginning, go up to the length of the [63:28] anagram. So, here uh the size of the [63:30] window or the K is really just the size [63:33] of the anagram, right? [63:35] And so, this will give me just the first [63:37] uh we'll say K characters of the string [63:40] and I'll put that into my counter. [63:42] Great. Now, from here, I can actually [63:44] initialize the count that I'm eventually [63:47] going to return. [63:49] So, I'll call it my we'll say num [63:51] matches. [63:53] And it could either be initialized as a [63:55] one or a zero depending on what my [63:57] initial window looks like, but I know at [63:59] the very end I'm going to just return [64:02] the num matches. [snorts] [64:04] And so, uh like we always say for our [64:06] sliding window of a fixed-size [64:07] algorithm, you have to watch out and be [64:09] sure to check your initial window. So, [64:11] I'm going to assign num matches as one [64:14] if the anagram counter is the same as [64:17] the window counter, [64:19] right? Otherwise, it's not the same, so [64:22] I'll initialize it to zero, right? I'm [64:24] just checking if the uh window has the [64:26] same count as my anagram, right? In [64:28] Python, the counter object's really [64:30] useful uh because you could just check [64:32] for equality using double equals. All [64:34] right, from here I enter my general [64:35] algorithm, so I need to slide my window. [64:38] So, I'm going to say for we'll say I [64:40] in range, and I want to go from the [64:43] beginning of the string, so just zero, [64:46] and then up to length of S minus the [64:49] length of anagram. You want to slide all [64:51] the way to the right as far as you can. [64:54] What I want to do is remove my uh [64:56] trailing character. So, if you wanted [64:58] to, you can split this up into some [64:59] variables, maybe you can say [65:01] trailing char is going to be your S at [65:06] index I, [65:08] and then, like you expect, your leading [65:10] char [65:12] is going to be S index I [65:15] uh plus [snorts] [65:16] the length of the anagram, right? [65:20] Cool. So, you have your trailing char [65:21] and your leading char. When it comes to [65:22] your trailing character, what you want [65:24] to do is just remove it from your count. [65:26] So, I can say my window counter access [65:28] the trailing char and just decrements [65:30] it. [65:31] And in the same vein, you also want to [65:34] uh increment [65:36] your leading character. [65:38] Cool. Now that you've slid your window [65:40] to the right, you just want to perform [65:41] your check here. Check if your newly [65:43] adjusted window [65:45] is actually a match with your anagram. [65:48] And if it is, then you can just [65:49] increment num matches. [65:52] Just some basic counting logic here. [65:55] All right, let's go ahead and give us a [65:57] test run. [65:58] Because we're in Python, we really get [65:59] to benefit from the built-in counter [66:01] collection, and it's really easy to [66:02] solve this. [66:04] Uh do you notice how similar this code [66:06] is compared to our previous, you know, [66:07] sliding window algorithms, right? We [66:09] still have this concept of initializing [66:11] our very first window. We have to [66:14] manually check it. Be sure to do that. [66:15] So, you know, if we have an initial [66:17] match, we initialize our count to one, [66:19] otherwise it's zero. Then from there, we [66:21] just slide our window to the right using [66:23] like the general part of the algorithm. [66:24] Like you expect, uh whenever we move to [66:27] the right, we remove our trailing [66:28] element from the collection, and we add [66:30] in our leading element. And then because [66:32] this is a counting problem, I just want [66:34] to go ahead and uh verify, uh do I [66:36] actually have a match for my window to [66:38] the anagram? If we do, we just increment [66:40] our global count here. Like we said in [66:42] the approach video, uh this code has an [66:44] N times K complexity, right? So, if I [66:47] kind of break things down here, [66:49] when we convert the anagram, which is of [66:51] size K, right? When we convert our [66:52] anagram into a counter, of course we [66:54] have to iterate through it under the [66:55] hood. So, that's really K steps. Uh [66:57] similar when we also convert uh just the [67:00] first few characters or the first K [67:01] characters of our string into a counter, [67:04] that would also be doing K iterations, [67:06] right? [67:07] And then doing this check over here, [67:08] right? This is a really important [67:09] aspect. Although we're doing like a [67:11] equality, it looks like a simple [67:12] operation, we are comparing two counter [67:15] objects, right? In Python, it will [67:17] literally check, you know, every key of [67:19] the counter if it's corresponding [67:21] frequency uh matches the other counter, [67:24] right? And so, in the worst case, I [67:25] would have K different keys in each of [67:27] these counters. So, this simple equality [67:30] check, it's actually not so simple. It [67:32] does take K steps. I know it's going to [67:34] be K because the biggest the window [67:36] counter is going to get is K, and I also [67:38] know that the anagram counter is exactly [67:40] K, right? [67:42] So, I have a bunch of Ks at the start. [67:44] When it comes to this for loop here, [67:45] here we're really iterating uh roughly [67:47] through the length of our string S, [67:49] right? So, that's really starting to [67:51] give us an N. [67:53] Now, if you look at the operations [67:55] inside of uh this for loop, this is [67:57] constant time, this is constant time. [67:59] All these operations are constant time, [68:01] except for this over here. Just like it [68:03] was before, because I'm checking for a [68:06] equality between my counter objects, [68:08] under the hood, this has to go through [68:10] each key and uh verify that the [68:12] frequency is the same. And like we [68:13] already said, that was K steps. So, this [68:16] nested operation is K. And just to be [68:18] clear, I'm going to put it over here. [68:19] So, it's really NK for this entire for [68:22] loop. [68:23] And so, looking at our kind of overall [68:25] complexity here, we have a K plus a K [68:26] plus a K plus an NK. Uh obviously, NK is [68:30] much bigger than any of these other Ks. [68:32] So, that's why the overall complexity [68:33] here is N times K. And that was the time [68:36] complexity. When it comes to the space [68:37] complexity, we're just looking at O of K [68:39] from all of these counters. [68:43] Hey programmers, Alvin here. Right now, [68:45] I want to go over the approach you can [68:46] use for the find subarray sum problem. [68:49] So, in this problem, we're going to be [68:50] given an array of numbers as input, as [68:52] well as some target sum. What I want to [68:55] do is find a subarray that sums to the [68:57] given target. [68:58] And so, for this particular input, the [69:00] answer would come from this subarray [69:02] over here where I have the two, one, and [69:04] the seven because 2 + 1 + 7 is 10. And [69:07] in the long run, you actually want to [69:09] return the start and end indices of that [69:11] subarray. [69:13] So, what I'm saying is if you actually [69:14] label all the indices of this array, of [69:16] course your indices start at zero, the [69:18] starting index is four and the ending [69:20] index is six. [69:22] And notice that here those indices [69:24] bounds for the start and end are [69:25] inclusive. So, just bear that in mind. [69:29] So, what this problem is asking is [69:30] pretty straightforward, but how can we [69:31] go about solving it? [69:33] So, lately I've been showing you the [69:34] sliding window algorithm. We know that [69:36] generally the sliding window algorithm [69:38] is really great at considering a [69:40] subarrays or substrings. [69:42] And so far in the course, we've always [69:44] been dealing with a sliding window of a [69:46] fixed size. But, you actually won't be [69:49] able to use that exact algorithm here [69:51] because you really need to find a [69:53] variable size. Meaning you won't know [69:55] exactly how big the subarray is that's [69:58] going to be the final answer, right? In [70:00] this particular input, it happened to be [70:01] a subarray of three elements, but [70:04] there's no constraint here, right? It [70:05] could have been two elements, it could [70:06] have been one element, it could have [70:08] been five elements. And so, you need to [70:10] consider windows of variable size. [70:13] Don't worry, though. We'll be able to [70:14] use a lot of the logic from our previous [70:16] renditions of sliding window. We just [70:18] have to adjust for some different things [70:19] here. [70:21] And so, for the sliding window with a [70:22] variable size, you want to start the [70:24] algorithm in a similar way where you [70:26] deal with some indices, right? [70:28] And so, I'm going to have in red my [70:30] starting index. And in green, I'm going [70:32] to have my ending index. And at the [70:34] beginning, you have them point at the [70:36] very first index. [70:37] And so, just so we don't forget it, my [70:39] start is red and my end is green. [70:42] And because overall you want to consider [70:44] the sum of a subarray, you're going to [70:46] have a sum variable. The sum variable is [70:49] going to represent the total sum of the [70:50] current window that you're looking at. [70:53] And so, how does this algorithm run? [70:55] Well, what you want to do is look at [70:56] your ending pointer and just add that [70:59] element into your sum. So, I'm going to [71:01] add the three into my sum. That means my [71:03] total sum is three. And so, you're [71:05] looking at this window here, right? [71:08] Notice that my start and end are [71:09] pointing to the same single element. So, [71:11] that would just be the subarray with one [71:14] element inside. That element is just [71:16] three. [71:17] And at this point, you could also, you [71:18] know, check your sum. So, I'm going to [71:19] check is my current sum of three equal [71:22] to my target? It's not. So, what I can [71:24] do is just increase the size of my [71:26] window. So, I'm going to slide the end [71:29] pointer to the right by just one [71:31] position. [71:32] So, now I'm looking over here. [71:34] Of course, at this point, you should [71:35] also add that one into your sum. So, I [71:37] do one plus my current sum of three. [71:39] That gives me four. And again, you [71:41] should continue to check. I'm going to [71:42] check if my current sum of four is equal [71:44] to my target of 10. It's not. So, I can [71:47] keep increasing here. [71:49] So, now I'm considering this element. [71:51] So, I add that four into my current sum. [71:54] My current sum is eight. I compare it to [71:55] the target. Eight is not equal to 10. [71:58] So, I keep going. [72:00] At this point, I add a nine into my sum. [72:02] That gives me 17. I check 17 is surely [72:05] not equal to my target. So, I need to [72:07] keep going. However, there's an [72:09] important thing to consider here. Now [72:11] that my sum is 17, when I compare that [72:14] to my target sum of 10, I really [72:16] overshot it. A really important [72:18] constraint they give us in this problem [72:20] is that they tell us that the input [72:22] array contains non-negative elements. [72:25] Because there are no negative elements [72:26] in the array, if I'm to continue to [72:28] increase the size of my window, that [72:30] would only make my sum larger and [72:32] larger. [72:33] So, it's 17 now. It's only going to get [72:35] bigger than 17, right? If I look at my [72:37] next element, I would have to add a two [72:39] into my sum. And I'm just getting [72:40] further and further away from the target [72:42] cuz I've already overshot it. So, here's [72:44] where we work in the interesting logic. [72:46] So far, we've only been incrementing uh [72:49] the position of our ending pointer. But [72:51] now, it's time to actually increment the [72:53] position of our starting pointer. [72:55] So, I want to pay attention to the red [72:57] pointer now. [72:59] And I want to actually move this one to [73:00] the right. That acts as my trailing [73:02] element. So, when I move this pointer to [73:04] the right, that would be effectively [73:06] removing the three out of the sum. I [73:08] subtracted the three from the 17, that's [73:11] why my current sum is 14. And I want to [73:13] do a check here. I'm going to compare my [73:15] current sum of 14, and I see that it's [73:17] still larger than my sum of 10. So, I [73:19] could move this start pointer even one [73:21] more position, shrinking the size of my [73:23] window. Of course, I remove the element [73:25] out of it. So, now my sum is 13. 13 is [73:28] still bigger than my target sum of 10, [73:30] so I should still shrink my window by [73:31] progressing adjust the starting pointer. [73:34] Because my current sum of nine is less [73:36] than my target sum, it's okay to [73:38] actually increase the size of the [73:39] window. When you increase the size of [73:41] the window, you just increment your [73:43] ending pointer. [73:44] So, you take the two. That means that [73:46] your current sum is now 11. 11 is too [73:49] big, right? 11 is bigger than your [73:51] target of 10, so you need to shrink your [73:52] window again. [73:54] Now, I'm just looking at the window of [73:56] just the single element two. [73:58] Two is less than my target sum, so I [74:00] grow my window. [74:02] I now have three. Three is less than my [74:03] target sum, so I grow my window. [74:06] And at this point, I've actually found [74:07] the target. Right, my current sum is 10, [74:10] and my target sum is also 10. [74:13] At this point, you just want to return [74:14] the indices of the sub-array that you're [74:16] looking at. [74:18] In this case, it would be the four and [74:19] six. So, there are two key steps here. [74:22] Whenever your current sum is less than [74:24] the target, you need to increase the [74:26] size of your window by incrementing your [74:29] ending pointer. [74:30] However, if your sum is too big, if your [74:32] sum is bigger than the target, you need [74:34] to decrease the size of the window by [74:37] incrementing the starting pointer. [74:39] If you do it this way, you'll eventually [74:41] be able to find the right target sum. [74:43] And along the way, you're considering uh [74:46] all of your windows are variable size. [74:49] The way we implement this is pretty [74:50] interesting, so I'll save that detail in [74:52] the code walk-through. [74:53] That being said, let's talk about the [74:54] complexity here. [74:56] If we say that n is the length of the [74:58] array, the time complexity here is just [75:00] O of n. [75:02] And I think that might be a little [75:03] surprising. A common mistake I see [75:04] students make when they look at the [75:06] drawing for this algorithm is they have [75:08] a feeling that it's going to be an n [75:09] squared algorithm. [75:11] I think that's like a reasonable [75:12] assumption to make, especially because [75:14] we have, you know, uh two pointers and [75:16] it looks like that they loop uh through [75:18] the same array. [75:20] But let's actually go through what an n [75:21] squared would look like. [75:23] So, looking back at my diagram here, [75:25] I'm going to step through what to me is [75:27] classic n squared behavior. I'll call it [75:30] my n squared-ish behavior. [75:32] And so, I'm going to start both of my [75:33] pointers just at the beginning, and if I [75:35] had a very typical like n squared nested [75:37] loops, it would look like this. [75:46] What you'll notice is a very key [75:48] characteristic of n squared-ish behavior [75:50] is that once you one of your pointers [75:52] gets to the end of the array, it has to [75:54] get reset like so. [75:56] And it keeps progressing. [75:58] So, that's what very classic n [76:00] squared-ish behavior looks like. And you [76:02] get it commonly from your nested loops. [76:04] However, we don't have that same pattern [76:07] here. So, I'm going to reset my drawing, [76:09] and just looking at the pointers, I'm [76:11] going to show you exactly how our [76:12] pointers were updated. It looked like [76:15] this. [76:19] And at this point in the trace, we would [76:21] have actually found the correct answer [76:22] cuz we have our sum of 10. But let's say [76:25] that we didn't find the answer, and we [76:26] had a lot more elements in the input [76:29] array. [76:30] If I had to keep searching, they might [76:31] behave something like this. [76:39] What you'll notice is, compared to my n [76:40] squared example, both of these pointers [76:42] here don't actually ever get reset. They [76:45] both generally just make progress by [76:47] sliding to the right. So, we actually [76:49] don't have N-squared here. What you [76:51] really have is 2 * N. [76:54] The two comes from the fact that we have [76:55] two pointers. The N comes from the fact [76:58] that each pointer needs to make its way, [77:00] in the worst case, through the entire [77:02] length of the array. Like you already [77:04] know, when I have 2N in my big O [77:05] complexity, I can just drop the constant [77:07] factor of two, giving me O of N. That's [77:10] why your time complexity here is just O [77:12] of N. Very clever stuff. [77:14] And the space complexity is constant [77:16] because you already know why. [77:18] All right, so that's the approach we can [77:19] use for this one. I think you should go [77:21] ahead and just start watching the [77:22] walk-through video for this. It's going [77:24] to be our first time implementing the [77:25] sliding window with a variable size [77:27] algorithm. It's somewhat similar to the [77:29] fixed-size algorithm, but it has some [77:31] major differences. The logic gets pretty [77:33] tricky, so you'll want to see me in the [77:35] walk-through video. [77:37] Hey programmers, Alvin here. Right now, [77:38] I want to go over the Python [77:39] walk-through for this find subarray sum [77:41] problem. Like we said in the approach [77:43] video, we want to solve this one using [77:45] our sliding window algorithm, but this [77:46] time we're going to implement it using a [77:48] variable-size window. So, I'm going to [77:50] need to set up a few variables. I'm [77:52] going to first set up some index I can [77:55] use to represent the start of my window. [77:57] Just call it start, initialize it to [77:58] zero. [77:59] I also need a way to track the sum of my [78:01] window. [78:02] So, I'll call it my window sum, also [78:04] initialize it to zero. From here, what I [78:06] want to do is set up a for loop that [78:08] iterates through my ending index. So, [78:10] I'm going to say for end [78:12] in range, it's going to start the very [78:13] beginning and just go through the length [78:16] of your list here. [78:18] So, now that I have the ending index of [78:19] my current window, what I want to do is [78:21] start accumulating the sum by using the [78:24] element at this end index. So, what I'm [78:26] saying is I could do window sum plus [78:28] equals, just add the element of your [78:30] list from this ending index. [78:33] This would be analogous to adding in the [78:36] leading element into your window, right? [78:39] Great. [78:40] But like we said in the approach video, [78:42] the interesting part about this [78:43] algorithm is I do need to make my window [78:45] smaller sometimes, right? Based on the [78:47] criteria of the problem, right? I want [78:49] to find a subarray that matches the [78:51] given target sum. [78:53] And if ever I have a window sum that's [78:54] too big, then I know I need to decrease [78:57] my window size, right? I could remove [78:58] some elements out of my window. [79:01] So what that would look like is like [79:02] this. I could say while my window sum [79:04] while big. So if it's bigger than my [79:06] target sum, then I'm too large, so I [79:09] should make it smaller. To make it [79:10] smaller, you want to remove elements out [79:12] of your window. And like all of our [79:14] previous sliding window problems, when [79:16] you remove something out of your window, [79:18] generally you want to remove your [79:19] trailing element. So that would be the [79:21] element at the start index. [79:23] So what I'll do is I can say window sum [79:26] - = [79:27] nums at the starting index. [79:30] So now that you've removed that trailing [79:32] element uh from your window, you do want [79:34] to also increase that starting index. [79:37] Start + = 1. [79:39] This has the effect of making my window [79:40] smaller. [79:42] And do you note that I have uh this code [79:44] in a while loop. So it's going to run as [79:46] many times as needed. So uh however long [79:49] the window sum is bigger than the target [79:51] sum, I'm going to keep removing elements [79:53] out of my window at the front. [79:55] So that means that when this while loop [79:57] is done, that means that my window sum [79:59] is no longer greater than the target [80:01] sum. It might actually be equal to the [80:03] target sum. So I'm going to check if my [80:05] window sum is equal to the target. And [80:07] if that's the case, then I just found [80:09] the answer, right? Here they tell us to [80:10] return the start and end indices of the [80:12] window that has the given target sum. So [80:15] for you in Python, just return a tuple [80:18] of the start and end. [80:20] So if my window sum equals the target, [80:21] then I go ahead and return the final [80:23] answer. If not, then I just go to [80:25] another iteration of this for loop and [80:27] just progress my ending uh index. Which [80:30] would mean that I add an additional [80:32] element into my window, perform the same [80:34] operation again and again. [80:36] Great. Let's go ahead and test this out. [80:40] And there we have it. I will say that [80:42] although this code is really short, I [80:44] think it's a little tricky in its [80:46] design, right? I do want you to really [80:48] understand how [80:49] this code uh corresponds to the drawing [80:52] we made during the approach video, [80:54] right? So, in particular, how this while [80:56] loop works, right? It just removes uh [80:58] elements uh out of my window sum uh if [81:01] ever my window sum is too large, right? [81:04] That gives me the effect of being able [81:05] to have a window of variable size cuz I [81:07] decrease my size when it gets too big. [81:10] And like we also said in the approach [81:11] video, this code's going to have an O(n) [81:14] runtime where n is the length of the [81:15] nums list, right? Although there are two [81:18] loops here, you do not have a n squared [81:21] uh runtime. And we did a big explanation [81:23] of that in the approach video, so go [81:24] back to it if you need. [81:26] When it comes to the space complexity, [81:27] it's pretty plain to see here that we [81:28] only have a constant amount of space [81:30] just coming from a few variables that we [81:32] use. [81:33] All right, programmers, that's all I got [81:34] for this one. Coming up next, we're [81:35] going to practice a lot more of these [81:37] sliding window of a variable size [81:39] algorithms. [81:42] Hey, programmers, Alvin here. Right now, [81:44] I want to go over the approach we can [81:45] use for this longest subarray sum [81:47] problem. [81:48] So, this problem is going to be just a [81:49] variation of the last one. So, we're [81:51] given an array of some numbers, and in [81:53] the problem, they do tell us that the [81:54] elements of the array are going to be [81:56] non-negative. We're also given a target [81:59] sum. [82:00] What we want to do here is return the [82:02] length of the longest subarray that sums [82:04] to the given target. For this particular [82:06] input, the answer we should return is [82:08] four, and that comes from this subarray. [82:11] Notice that the elements in the subarray [82:13] do indeed sum up to my target sum of 10, [82:15] and it happens to be the longest [82:16] subarray possible that adds up to 10. [82:19] Bearing in mind that we want to return [82:20] the length of that subarray. [82:22] All right, so that's what the problem is [82:24] asking. Uh how can we go about solving [82:25] this one? Well, we're going to use our [82:27] sliding window algorithm. We know [82:29] sliding window is a good fit here [82:30] because we need to consider all possible [82:32] sub arrays. And because we don't know [82:35] the size of the potential sub array, you [82:37] want to do the sliding window with a [82:39] variable size, right? And so, let's go [82:41] over how this works again. It's going to [82:43] be very similar to our last problem, [82:44] just giving us another opportunity to [82:46] practice. [82:47] So, what I'm going to do is I'm going to [82:48] track a key variable. I'm going to track [82:50] the sum of the elements in my current [82:52] window. [82:53] We also need to set up some pointers. [82:55] I'm going to have in red the starting [82:56] index of my window, and in green I'm [82:59] going to have the ending index of my [83:00] window. So, the way this algorithm works [83:02] is I want to add my ending element, so [83:06] the element being pointed to by the [83:07] green arrow, I want to add that into my [83:10] sum. So, I'm going to add this four into [83:12] my initial sum, giving me a current sum [83:14] of four. And I'm considering this very [83:17] initial window, right? Just containing [83:18] the elements four. [83:20] And of course, because you want to look [83:21] for your target sum here, you would [83:22] check if your current sum of four is [83:24] equal to your target sum. It's not, so [83:26] you can keep running this algorithm, [83:28] right? So, I just want to increment my [83:30] ending pointer, [83:32] adding another element into my window. [83:34] Now my sum is seven. It's still too [83:36] small, so I'm going to take another [83:37] element. Now I take the three. Notice [83:40] that right now my sum is right on the [83:42] money, right? My sum of 10 is equal to [83:43] the target sum of 10. [83:45] And because in the long run I want to [83:46] find the largest window that matches up [83:49] to 10, what I want to do is just save [83:51] this in some longest variable. [83:53] So, so far the longest sub array that [83:55] sums up to the target, that would be a [83:57] length of three. Notice that I'm going [83:59] to be saving in longest the length of [84:01] the sub array. And I can easily figure [84:03] out how many elements are in my window [84:05] by just looking at my pointers, right? [84:07] There are three elements in my window [84:08] because my start and end pointers are [84:10] inclusive. [84:12] Great. At this point I keep running my [84:14] algorithm, and what you should do is [84:15] actually still increment your green [84:17] pointer. So, you're going to grow the [84:18] size of the window. [84:20] And when you do this, you'll see that [84:23] it's the case that actually my sum is [84:24] too large now, right? I know that I'm [84:26] looking for a target sum of 10, but I [84:29] went over to 12, right? Because they [84:31] tell us in the problem that our array [84:34] only contains non-negative elements, if [84:36] I were to increase my window more and [84:39] more, I would just get farther away from [84:41] the target sum cuz I would get larger [84:42] and larger potentially. So, at this [84:44] point, I'm too large, so I should [84:45] decrease my window size. To decrease [84:48] your window size, you just want to [84:50] increment your red pointer or your [84:51] starting pointer. And when you do that, [84:53] you would remove that element of four [84:55] from your sum. [84:57] Great. Now, it's the case that my [84:59] current sum is okay, right? It's now [85:01] below 10, so I can keep incrementing it [85:03] if I need. Whenever your window sum is [85:05] less than your target, you can just [85:07] increase the size of your window taking [85:09] a new element. It's still the case that [85:11] I'm below the target sum, so I'm going [85:12] to grow the size of my window. [85:15] But at this point, I go over to 14, [85:18] right? So, now I'm too large. So, now I [85:19] need to decrease the size of my window. [85:22] I'm down to 11, but it's still the case [85:24] that I'm still over the target sum, so I [85:26] decrease again. [85:28] That brings me to a window sum of eight. [85:30] At this point, I'm good to go, but I [85:32] still need to find my target sum of 10, [85:34] so I keep increasing the size of my [85:36] window by progressing that ending [85:38] pointer. [85:40] At this point, I'm right on the money. [85:42] My current window sum is 10, my target [85:44] is also 10, and if I actually look at [85:46] the number of elements in my window, I [85:47] have four elements in my window. That's [85:49] actually more elements than the current [85:51] longest I have stored. So, now four is [85:53] my new longest, and I continue my [85:55] algorithm. I still want to increment my [85:57] ending pointer, growing the size of my [85:59] window. [86:00] This brings me up to 13, which of course [86:02] is too large, so now I decrease the size [86:04] of my window. [86:06] I'm still too large, so I do it again. [86:09] So, here I hit my target sum, but if I [86:11] look at the number of elements in my [86:12] window, I currently have a window size [86:14] of three, but the longest I've seen is [86:16] four, so I don't do any replacing here, [86:18] right? Cuz this three is smaller than [86:21] that four over there. [86:22] So, I keep running. So, I increase my [86:24] window size, but now I'm too large at [86:26] 15, so I need to decrease it. [86:29] Here I'm at 10, and again, it's another [86:30] case where I have three elements in my [86:32] window, but my longest is four, so I [86:34] just continue on. I don't do any [86:35] replacing here. [86:37] I take my next element, I go all the way [86:39] up to 20, which of course is too large, [86:41] so I decrement my window size by [86:43] progressing that starting pointer. [86:45] And I need to do that a few times until [86:47] I get down below my threshold. At this [86:50] point, I actually hit my target sum of [86:51] 10, but of course, my window size is [86:54] only one, and it doesn't get to replace [86:56] the four. [86:57] So, I continue my algorithm. I grow my [86:59] window, bring me up to 11. So, now I [87:01] need to make my window smaller. If I try [87:03] to continue the algorithm further, I [87:05] actually hit the end of my input array. [87:07] So, I know that I've exhausted uh all [87:09] possible sub-arrays uh to look at. And [87:12] so, I can just return what I have stored [87:14] in longest, which is the final answer of [87:16] four. [87:17] So, that's all there is to this [87:18] algorithm. Uh very similar to our [87:20] previous problem. If you say that n is [87:21] the length of the array, the time [87:23] complexity here is just O of n. In the [87:26] previous problem, we did a long uh trace [87:28] through for why the complexity is O of n [87:30] and not something like an n squared. The [87:32] short story is that in this problem, we [87:34] need to actually progress uh both [87:36] pointers all the way through the array. [87:39] So, it's going to take n steps to move [87:40] the red starting pointer through the [87:41] array, and it's going to take another n [87:43] steps to move the green ending pointer [87:45] through the array. So, that's two n [87:47] iterations overall, which just [87:48] simplifies to O of n. [87:51] The space complexity here remains [87:52] constant cuz we're just using a handful [87:54] of variables for our window sum as well [87:56] as the longest length we've seen thus [87:58] far. All right, programmers, I want you [88:00] to try to code this one up on your own. [88:01] You're going to see that the code is [88:02] almost identical to our previous problem [88:04] just with a little spin. That way you [88:06] get to practice this concept. [88:08] If you get stuck, you can find me in the [88:09] walk-through video. [88:11] Hey programmers, Alvin here. Right now, [88:12] let's go over the Python walk-through [88:14] for the longest subarray sum problem. [88:16] So, this is going to be just a spin-off [88:17] of our last problem, and we're going to [88:19] use that sliding window with a variable [88:21] size algorithm. So, we're going to begin [88:23] with our starting index at zero. I do [88:25] need to track the longest window over [88:27] time, so I'm going to uh set my longest [88:29] equal to zero. I also need to track the [88:31] sum of my current window, so I'll set my [88:33] window sum [88:35] equal to zero. [88:37] From here, I want to iterate through my [88:38] end of my window. So, I can say for end [88:41] in range from zero, [88:43] go up to the length [88:45] of the nums. [88:47] And what you want to do is uh take the [88:50] elements at these ending indices and add [88:52] them into your window. So, that'll be my [88:54] window sum plus equals [88:56] nums at end. [88:59] Great. [89:00] From here, what you want to do is uh you [89:02] do need to correct your sum if it gets [89:05] too large. In other words, if my window [89:07] sum is too big, if it's bigger than the [89:08] target, then I know I need to bring it [89:10] back down by reducing the size of my [89:12] window. So, you can do that by [89:14] progressing the starting index. But, be [89:16] sure to also remove the corresponding [89:18] elements out. So, I can say window sum [89:20] minus equals [89:22] nums [89:24] at start. [89:26] Great. Now, from here, you just want to [89:28] go do your uh max value logic. So, I'm [89:30] going to set the longest equal to the [89:32] maximum between the length of my current [89:34] window. The length of your current [89:36] window would just be end minus start [89:39] plus one. [89:40] And also, compare that against what you [89:41] currently have in longest. [89:43] Great. [89:44] Now, after your for loop is done [89:45] running, just return the longest. This [89:48] code has a very similar shape to our [89:49] last problem. [89:51] You might be wondering about this trick [89:53] here. So, this just gives us the length [89:55] of the current window, and we've seen [89:57] this arithmetic before, but I'll review [89:58] it over here. Let's say we had just some [90:00] abstract elements here. [90:03] E F. I'll label their indices, so 0 1 2 [90:07] 3 4 and 5. [90:10] And let's say I just had um some [90:12] particular values for my end and start. [90:14] Let's say my end is maybe [90:17] the E element. And then my start, we'll [90:21] say my start is the B element here. [90:25] Great. So, I want this quantity to be [90:28] the number of elements in the window. Do [90:29] bear in mind that my start and end [90:32] indices are inclusive, right? So, if I [90:35] do end minus start, I'll do 4 minus 1, [90:38] that gives me 3. Then I do this [90:40] additional plus 1, and that gives me 4, [90:42] cuz there are four elements in this [90:43] window. [90:44] One thing I am forgetting here is be [90:46] sure to actually uh check if your window [90:49] sum uh reaches your target sum before [90:51] you actually do the max value logic. So, [90:53] you want to write an if statement here. [90:54] You want to check if your window sum is [90:56] equal to the target sum, [90:58] then you can do this stuff. [91:01] Great. Let's give it a test run. [91:03] There is another bug we need to fix, but [91:04] we can fix it together. [91:06] So, here we're passing the first test [91:07] case, but we're failing the second one. [91:09] Second one is a pretty obvious edge [91:11] case. Um here, this is a circumstance [91:13] where the target sum is actually not [91:16] found within the input list here, right? [91:19] There is no uh subarray that sums up to [91:21] five. In that circumstance, they want us [91:23] to return -1. [91:25] Looks like my code returns zero, right? [91:28] And that has to do with the default [91:29] value I chose for the longest, [91:31] right? [91:32] And so, what I want to do is actually [91:34] initialize this longest to be -1. [91:36] Because if I never find a window that [91:39] matches my target sum, then you're just [91:40] going to return the longest variable, [91:42] which it still contain -1. [91:44] So, let's give that a test run. [91:47] Great. And there we have it. So, like we [91:49] said in the approach video, the time [91:51] complexity for this is just O of N, cuz [91:53] we're moving the start index all the way [91:55] through the list once, and we're also [91:57] moving our ending index all the way [91:59] through the list once, right? So, [92:00] although we have nested loops here, we [92:02] don't have n squared. And we kind of [92:03] talked about why that was in the [92:05] previous problems. The space complexity [92:07] here just remains constant cuz we're [92:08] only dealing with a handful of [92:10] variables. All right, programmers. I [92:12] hope you're starting to get the hang of [92:13] the sliding window with a variable size [92:15] algorithm. Of course, we'll do some [92:16] variations coming up next. [92:18] Hey programmers. Now that we've done a [92:20] few sliding window with variable size [92:22] problems, I want to go over the recipe [92:24] for this one. [92:26] As always, sliding window algorithms are [92:28] a good choice whenever you need to [92:29] consider sub-arrays or sub-strings. If [92:32] your sub-arrays or sub-strings have any [92:34] size, then you want to use the variable [92:35] size version, as opposed to the fixed [92:37] size, of course. [92:39] So, let's go over the general steps for [92:41] this. [92:42] So, for the most part, you typically [92:43] want to begin by initializing your start [92:45] pointer to the very beginning of your [92:47] string or array. So, that would be to [92:49] index zero. [92:50] And then from there, you also want to [92:52] initialize another key variable. You [92:54] want to represent the window collection. [92:56] And this might vary from problem to [92:57] problem. So, as of late, our collection [92:59] has just been a sum that we add into. [93:02] But, of course, your collection can [93:03] really be anything, right? We've seen [93:04] for our sliding window with fixed size [93:06] algorithms, sometimes our collection [93:08] might be a set or it might be a hash [93:10] map. So, this really depends on the [93:11] context of the problem. But, typically, [93:13] you're going to have some collection [93:15] that represents the aggregate of the [93:17] window. [93:19] From there, we iterate the end pointer [93:21] through the array or the string. And [93:23] typically, we accomplish this with a for [93:25] loop. [93:26] There are a few different steps that [93:27] happen within this for loop. One thing [93:29] you'll always want to do is make sure [93:30] you add the leading element to the [93:32] collection. [93:33] Right? So, you want to add the element [93:35] at the end pointer into the collection. [93:38] What you also want to do is have a way [93:39] to remove trailing elements from the [93:41] collection. And this is a really [93:43] important step. And what you'll want to [93:44] notice is when you remove trailing [93:46] elements from the collection, you might [93:47] have to do that multiple times cuz you [93:49] want to continually remove trailing [93:51] elements again and again while your [93:53] constraint is violated. And as you [93:56] remove elements, hopefully, eventually, [93:58] your constraint is met once again and [94:00] you're no longer in violation. So, in [94:02] the context of our previous problems [94:03] with our sum, whenever our sum got too [94:06] large, right? Then we started to remove [94:08] trailing elements from our sum to get [94:10] back down within that target sum. [94:13] Like I have highlighted here, you [94:15] typically do this removing of elements [94:17] using a while loop, right? This happens [94:18] many times until your constraint is met [94:21] once again. [94:23] So, these two steps of A and B give us [94:25] our variable-size window. Because step A [94:27] of adding the leading element to the [94:29] collection, that would increase the size [94:31] of our window. [94:32] Whereas step B of removing a trailing [94:34] element from the collection, that would [94:35] decrease the size of our window. So, [94:37] we're able to grow our window or reduce [94:39] our window as needed. [94:41] And finally, the fourth step is to just [94:43] do the business logic that's specific to [94:45] the problem you're trying to solve. And [94:47] this could be a few different things, [94:49] right? You might want to count [94:49] something, might want to determine the [94:51] max or min of something, or just find if [94:53] something exists. It really depends on [94:56] the specifics of the problem. And of [94:58] course, I'm going to show you a few [94:59] different variations of that coming up [95:01] next. [95:03] Before we hop into some more problems, I [95:04] just really want to emphasize the [95:06] importance of step B. To me, this is [95:09] what really makes the sliding window [95:11] with a variable-size algorithm, it makes [95:12] it special, right? It's how we remove [95:14] trailing elements from the collection [95:16] while our constraint is violated. [95:19] The important part of these algorithms [95:20] is really determining when we violate [95:23] our constraint and how we can actually [95:25] undo things to get back within that [95:27] constraint. [95:29] All right, so that wraps up my recipe [95:30] for the sliding window with variable [95:32] size. Do you bear in mind then that this [95:34] is just a broad guideline, right? You [95:35] might not exactly be able to implement [95:37] these steps to a T to solve every [95:40] sliding window with variable size. [95:42] Sometimes you'll have to adjust things. [95:44] But as we do more problems together, I [95:45] think you'll get a good sense of that. [95:47] All right, let's get to it. [95:50] Hey programmers, Alvin here. Right now, [95:52] let's go over the approach we can use [95:53] for this longest unique substring [95:55] problem. [95:56] So, in this problem, we're going to be [95:57] given just a string S as input. And what [95:59] we want to do is return the length of [96:01] the longest substring that contains only [96:03] unique characters. So, here the result [96:06] we should return is four. And that comes [96:08] from this corresponding substring. This [96:11] is the longest substring with no [96:12] duplicated characters. To solve this [96:14] one, what you want to do is use your [96:15] sliding window algorithm. Because we [96:18] want to consider different substrings, [96:19] and we also don't know how long the [96:21] substrings need to be, we're going to [96:23] use a sliding window with a variable [96:25] size, of course. [96:26] And so, like you always expect, we're [96:27] going to set up our pointers. In red, [96:29] I'm going to have my starting index for [96:31] my window. And in green, I'm going to [96:32] have my ending index for the window. [96:35] And because I want to ultimately return [96:36] the length of the longest substring, I'm [96:38] going to have a variable to track the [96:39] longest. You could just initialize it to [96:41] zero, right? Because you haven't found [96:43] any substring yet. [96:44] In order to track what characters you've [96:46] seen thus far, I think it's great if you [96:48] represent the characters that are [96:50] currently in your window using some sort [96:52] of counter hash map. In other words, [96:54] over time the keys of this hash map are [96:56] going to be characters. The [96:57] corresponding values are going to be the [97:00] counts of those characters within my [97:01] window. [97:03] Similar to some previous problems. [97:05] So, to start this algorithm, what I do [97:07] is I take the current element at my [97:09] ending pointer, and I add it into my [97:12] counter data, my window data. So, I'd be [97:14] looking at this initial window. So, I [97:16] take the A and just add it into my [97:17] counter. So, that means A is a key, and [97:20] now its count is one. [97:22] At this point, to be complete, we should [97:23] actually do our kind of like max value [97:25] logic. [97:26] Trivially, A is indeed a substring that [97:29] contains only unique characters, and its [97:31] length is one. So, one could actually [97:33] replace this longest of zero. [97:36] So, to continue the algorithm, I go [97:38] ahead and increase my window size. So, [97:40] now I take the B. If I look at my window [97:42] data, it's still the case that my window [97:44] contains only unique characters. I know [97:46] they're only characters because all of [97:49] the counts are one. [97:50] Because I have a current window size of [97:52] two, I actually replace that into my [97:54] longest. [97:55] And I keep running. Increase my window [97:57] size again by progressing the ending [97:59] pointer. [98:01] And it's still the case that I have [98:02] unique characters here. Of course, my [98:04] window size is three, so that becomes my [98:06] new longest thus far. [98:08] On the next iteration, I still try to [98:10] increase my window size taking a new [98:11] element. Uh but at this point, I see [98:14] that I no longer have unique elements [98:16] within my window because A hit a count [98:19] of two. If any of your character counts [98:21] are more than one, then you definitely [98:22] have a duplicate character inside. And [98:25] like we expect, now that we've violated [98:26] our window constraint, what we want to [98:28] do is now decrease the size of our [98:30] window until we're back within the [98:32] constraint. And so, what I do is I [98:34] increment my ending pointer, uh really [98:37] making my window smaller and removing an [98:39] element from the window. [98:41] Just like that. [98:42] And as soon as I do that, I actually [98:43] bring my window data back within the [98:46] constraint. It looks like everything [98:47] here is indeed unique. [98:49] The window size is three, and it's not [98:51] longer than the longest, so I don't need [98:52] to replace it here. At this point, I can [98:54] increase my window size, but as soon as [98:56] I do that, I violate the constraint, [98:58] right? Cuz B has a count [clears throat] [98:59] of two. So, what I want to do is now [99:00] decrease my window size till I'm within [99:02] constraint. [99:04] Now that I'm good, I can increase my [99:06] window size, but of course, as soon as I [99:08] do that, looks like C violates my unique [99:10] constraint. So, I decrease my window [99:12] size. I'm back within constraint now. [99:16] At this point, I increase my window [99:17] size. This actually gives me a new [99:18] character of Q, and I'm actually still [99:20] within constraint because all of my [99:22] character counts are less than two. [99:25] Notice that the length of my window now [99:26] is four, and four is bigger than three, [99:29] so I should take the four as my current [99:30] longest. [99:32] At this point, I can keep increasing my [99:33] window size, but this actually violates [99:35] the uniqueness of B. And so, I decrease [99:38] my window size, and this is actually a [99:39] really important scenario. Uh notice [99:41] that although I decrease my window size, [99:44] I still am violating my constraint cuz I [99:46] I didn't actually change the counts of [99:48] B. What I did was actually remove an A [99:51] out of my window data. That comes from [99:52] down here, right? So, when you actually [99:55] go ahead and try to make your window [99:57] smaller, when you're trying to get back [99:59] within the constraints of your window, [100:01] uh could be the case that you might need [100:02] a few iterations to get within that [100:05] constraint. And so, on this next [100:07] iteration, I do have to make my window [100:08] smaller again. [100:09] And this is actually where I correct [100:11] things, right? I get rid of that B, and [100:12] that's good because I'm no longer [100:13] violating my uniqueness constraint. [100:16] At this point, everything looks unique [100:18] and good to go, so I can go ahead and [100:19] make my window bigger. [100:20] At this point, I violate B once more, so [100:22] I need to make my window smaller. I get [100:25] rid of the C, still violate, get rid of [100:27] the Q, still violate, and I get rid of [100:29] the B. Now, I'm actually back within [100:31] spec. Obviously, at this point, my [100:33] window is very small. Although I have a [100:35] unique substring, it only has a size of [100:38] one, so it surely doesn't get to replace [100:40] my longest. [100:41] At this point, if you try to actually [100:43] increase the size of your window, you [100:45] actually finished all of your [100:46] iterations. And so, you can just return [100:48] the value you have stored in longest. [100:50] So, your final answer is four. [100:52] So, like we expect here, if we say that [100:54] N is the length of our input string, the [100:56] time complexity is O of N, similar to [100:58] our previous sliding window of variable [101:00] size algorithms. Although we have to [101:02] slide both of our pointers through the [101:04] full length of the string, that really [101:06] gives us a 2N, right? The first N is for [101:09] me sliding the red pointer all the way [101:11] through the string, and the second N [101:12] comes from me sliding the green pointer [101:14] all the way through the string, right? [101:16] We don't get an N squared here, like we [101:17] always say. Here, the space complexity [101:19] is also going to be linear, coming from [101:21] the counter hash map that we maintain. [101:23] In the worst case, you might have a [101:25] whole bunch of different characters [101:26] within your counter hash map. So, [101:28] overall, you have linear time and space [101:30] for this one. [101:31] Hey programmers, Alvin here. Right now, [101:33] let's go over the Python walk-through [101:34] for this longest unique substring [101:36] problem. [101:37] So, as always, like we've been doing as [101:39] of late, we're going to solve this one [101:40] using our sliding window with a variable [101:42] size. And this time we're dealing with [101:43] some some strings, right? So, I want to [101:45] mess with some character counts. [101:47] So, since you're doing this in Python, [101:48] you have the luxury of maybe using the [101:50] built-in counter collection. [101:52] So, I'll say from collections [101:55] import [101:56] Counter. [101:57] And I'll initialize one down below. [102:00] I'll call it my, I don't know, window [102:02] counter. [102:03] And what are some other variables that [102:05] we're going to need here? Well, typical [102:06] for most of your sliding window variable [102:08] size algorithms, you're going to need [102:11] the start index. [102:13] And because here I'm ultimately [102:14] concerned with returning the length of [102:16] the longest unique substring, [102:18] going to have a longest variable. [102:21] I'll initialize that longest length to [102:22] be zero. Of course, I'm going to replace [102:24] it over time using some max value logic. [102:27] So, from here, I want to iterate through [102:28] all of the end indexes. So, I'll say for [102:32] end in range, [102:34] go from zero up to the length of the [102:36] string. [102:38] Cool. [102:39] And what I want to do is I'll go ahead [102:41] and grab um the character at this index. [102:44] So, I can say S [102:47] at end. And cuz I'm going to need to [102:49] reference it a few times, this might be [102:50] a little cleaner to have a variable. [102:51] I'll call it my leading character. [102:54] Some familiar naming for us. [102:56] Great. The nice part of using the [102:57] counter collection in Python is that you [102:59] can just go ahead and start by [103:01] incrementing your characters because if [103:04] a key does not yet exist inside of your [103:06] counter, it implicitly has a count of [103:08] zero. So, what I'm saying is I can take [103:10] window counter [103:11] of leading char and just [103:14] increment it immediately, right? This is [103:16] safe to do. Uh even if the um leading [103:19] character does not exist explicitly as a [103:21] key in the counter, it implicitly has a [103:25] key, right? It's corresponding value is [103:27] zero, so now I increment it if it's the [103:28] first time. [103:29] Great. So, that gives me a way to add [103:31] elements or characters into my window. [103:33] Now, I need a way to remove them. So, [103:35] when should you remove characters here? [103:37] Because in the long run, you want to [103:38] find the longest unique substring, you [103:41] want to remove characters while you're [103:43] non-unique, right? If ever you violated [103:45] your constraint, you're going to keep [103:47] removing stuff until you're back within [103:49] that constraint. So, I want to consider [103:50] the character I just added, and I want [103:53] to uh make sure that it's unique. [103:56] So, I'll actually just grab this here. [103:59] So, if it's non-unique, so if its count [104:01] is bigger than one, then I need to keep [104:03] removing stuff, right? So, I need to [104:04] remove a character here. You always want [104:06] to remove from the uh back of your [104:09] window. So, that'll be S start. [104:12] And I'm going to use some familiar names [104:14] here. I'll call this my trailing [104:16] char. [104:18] And so, first I'll decrement the count [104:20] in the window counter. [104:22] So, window counter of trailing char [104:24] -= 1. [104:26] And because you're making your window [104:27] smaller, be sure to increment the start, [104:29] right? Start += 1. [104:32] Great. [104:33] So, this while loop is going to remove [104:34] as many characters as I need until I'm [104:36] guaranteed that uh my substring is now [104:39] unique. [104:40] So, now that I have a unique substring, [104:42] I want to do the max value logic. So, [104:43] we'll just set longest equal to the max [104:46] between the current window length, which [104:48] is end minus start plus one, [104:50] and then compare that against the [104:51] longest you have stored thus far. And [104:53] you've seen kind of the math behind this [104:55] a few times by now. [104:57] After your for loop is done running, [104:58] just return [105:00] whatever you have stored in longest. [105:03] Great. [105:04] So, very typical structure here, right? [105:06] We have our while loop inside of a for [105:08] loop. The while loop has the job of uh [105:10] bringing us back within the constraints [105:12] of the problem, right? To make sure we [105:13] have a unique substring here. [105:16] So, let's test it out. [105:17] Great. Looks like this is passing. [105:20] So, uh a few ways you can kind of write [105:21] this. Um I kind of wrote this for loop [105:24] so it iterates through the the kind of [105:27] index numbers directly. If you want, you [105:29] can do your fancy Python thing, so I'll [105:31] kind of leave that to you, but you know, [105:33] you could do stuff like enumerate. [105:36] Enumerate. If you enumerate S, you'll [105:39] have access to the ending index, right? [105:41] And you also have access to the element [105:43] itself, in this case the leading char. [105:45] So, you kind of skip this line here. [105:47] That would be functionally the same, a [105:49] little more Pythonic as well. If you [105:52] remember to use the colon. [105:53] Great, still passes. [105:55] Like we said in the approach video, this [105:56] code has an O of N run time, like our [105:59] previous problems, right? The only thing [106:01] that's unique about it now is actually [106:02] also has an O of N space complexity, [106:05] right? Of course, coming from the [106:06] counter we create. In the worst case, [106:08] we're going to have a key for every [106:10] character in from our input string here. [106:13] All right, programmers, that wraps up [106:15] our course on the sliding window [106:16] algorithm. We solved a bunch of problems [106:19] together. We started out with some basic [106:21] fixed-size window problems, and then [106:23] explored some advanced variable-sized [106:25] ones. This course might be over, but the [106:27] learning doesn't stop here. If you enjoy [106:30] my teaching style and want to practice [106:31] more sliding window problems, then you [106:33] should check out my full algorithms [106:35] course at structy.net. [106:37] There, I'll teach you everything you [106:38] need to know to pass your DSA [106:40] interviews. I'll leave a link in the [106:42] video description, if you're interested. [106:44] That's all for now. Thanks for watching.