Algorithmic Patterns for Coding Interviews: Sliding Window 1/4

hey what's up everybody in this video we're going to go over our first algorithmic pattern the sliding window pattern so what is the sliding window pattern well it's important to note that we can break the sliding window pattern down into two types one that uses a fixed window size and one that uses a dynamically sized window the problem will determine whether or not your window size will be fixed or dynamic which you will see examples of soon for now let's start with the fixed window size let's imagine that we have an array of integers and then let's imagine that we want to calculate the average of the values within a specific subset of that array for example say we are asked to calculate the average of a contiguous subarray of size 4 within this array contiguous just meaning that all four elements are adjacent or next to one another so for the sake of this example we'll do these first four elements first of all since the size of the subarray is given to us because we are asked to calculate the average of a contiguous sub ray of size four four is the size of our window a fixed size so we would add all four of the elements up and then divide the sum by four because to calculate the average for a set you simply take the sum of the numbers and divide it by the total number of values in the set now let's imagine that we need to find the maximum average when considering all contiguous sub-arrays of size 4 within the array sounds a bit complicated right well let's break it down how many contiguous sub-rays of size 4 do we have in this array remember that contiguous means that all four elements are adjacent to one another this tiny array is small enough for us to count these sets out so we have a set of four here here and here anything beyond that is no longer a sub array of size four so what we want to do is calculate the average for all three of these subsets and whichever has the highest average is our answer now there's a naive way to solve this which we are actually going to go over step by step this is the only time within this video that we will write code for the naive solution to a problem this is so that you can actually feel in your soul the benefit of using the actual pattern and by the way the problem that we are referring to currently is this leak code problem here so before we get into an example of the sliding window solution let's go over how not to solve this problem so the naive way to solve this problem would be to iterate through k elements for each element of our input array so for this first element of our input array we'd iterate through each of its elements up until k adding them to our sum then after we divide that sum by k then we'd move on to the second element of our input array and we would once again iterate through each element up until k adding the values to our sum and dividing that sum by k and then once again for our third element we'd do the same thing so at this point you've probably already noticed why this is inefficient but let's keep going let's write some code okay so before we get started with writing up our code you're going to want to install go if you don't already have it installed so to do that you just want to go to goling.org i'll put a link in the description and from this page you just want to hit download go and from here you will just select the package for your operating system i'm using mac so i would select this package and from here you will download an installer that is self-explanatory so just download and run this installer and once you have everything installed the only thing that you're going to need to pay attention to at this point is your go path and you can see what your go path is as well as check to see if go was installed correctly by just doing go environment go path and here it will show your go path and this path is generally just going to be a go folder within your home directory okay so to start i'm just going to create a directory in my go path source folder and i'm just going to call it youtube patterns and i'll just cd into that directory and within this directory i'll just create a file called bad max average subarray dot go i dot go and i'm just adding bad to the name because this is the naive solution so we'll go ahead and open that file and actually my vim is complaining so i'll just do go mod in it and then just go mod tidy and then i'll go back into the file and within this file i'll just add a comment to the top and i'll say leap code problem and we'll just take the problem number and name here and copy it and then go ahead and paste that to the top and just a quick note this problem actually isn't one of the problems in our leak code patterns list i'm using this problem to explain what sliding window is because it's relatively easy to understand so what we're going to need to do is we're going to need to call this package main and we'll go ahead and import format and math and then we're going to create our entry point which is just going to be a function called main and if you're unfamiliar with go you should have no problem following along with this tutorial because i go pretty in depth when explaining the code so if you're familiar with any other programming language i think that you should be fine with following along with this tutorial even if you don't have experience with go so we're going to create a variable for k which we're going to pass into the function that we create for this problem so the input for k is going to be 4 same as our example then we're also going to create an input array and to initialize an array literal of integers and go we're just going to do this and within these curly brackets we will add the numbers from our problem in the example so we can just take these numbers copy them and then paste them here as our input array values and then we'll set our answer equal to the returned value from our function which we will call find max average and then of course we'll pass in nums and k and after we get the answer we're going to print our answer so this is going to be our main func so whenever we run this file it's going to run this main function and it's going to pass these two values into this function that we haven't yet created so now let's create this function so we'll do func find max average and it's going to take in nums which will be an array of integers and it's going to take in k which will be an int it's going to return a float 64. and to start we're going to initialize a variable called max and its initial value is going to be negative infinity and in go this is how that's done we use the math package and we use this if method and the reason we want max to start off as negative infinity is because if we started off as zero which would be the default initial value if we were to compare a maximum average that's a negative number to zero the maximum that is returned would be zero instead of the negative value i hope that makes sense and if it doesn't it'll become more clear as we go on with writing this function so we're going to start with a for loop is less than the length of nums we're going to increment our i so we're going to iterate through nums which is the input ray containing the integers and for each iteration of nums we're going to create a window sum and we're going to set it equal to zero and also for each iteration of i we're going to iterate through k just like in our example so for j equals zero j is less than k j plus plus now as you saw in the video there's going to come a point where we reach the end of the array and if we go any further the subarray size is going to go beyond the array's size so to solve that issue we're going to write an if statement if not i plus k minus 1 greater than the length of nums minus one then we'll perform this code window sum plus equals nums i plus j so just like in the example before of the naive solution for each element of i we're going to iterate up to k elements and if this is sounding confusing right now don't worry i'm going to explain each line of code in detail after we finish writing this code so just bear with me for a bit if you can't understand it then we'll add else so if performing the above code in the if statement will bring us out of the range of the size of our array and we're going to instead set our i equal to length of nums and set our j equal to k and this is essentially just going to terminate the for loops and following the termination of the loops within our top level loop we still want to check if window sum is not equal to zero and if it's not we're going to set our max equal to whichever is greater our current max or the current sub arrays average so we'll do math.max and we're going to check if max is greater or float64 window sum divided by float64 k and the reason we're converting these to floats is because they're currently integers and if we divide an integer by an integer the resulting the result of the division is going to be an integer as well so if there's anything after the decimal point it will be removed so we're going to want the result of the division to be a float and once we do that outside of both of the loops we're going to check if max equals math.if so if max equals negative infinity we want to return zero we never want to return negative infinity but if that's not the case we're just going to go ahead and return our max and again if any of this is confusing to you don't worry just bear with me i'm going to go over it and try to help you visualize it in the next step so we can go ahead and save this file and let's clear and then let's go run badmax averages.go and the result we get is 12.5 as the maximum average which if you remember from the presentation 12.5 is the highest average the other two averages for the other two sub rays are 10.5 and 0.5 so now i want to take some time to go over every line of code to attempt to help you visualize what's happening here so let's do that okay so now let's take some time to try and visualize how this code is working so let's assume that we're going to be taking in the same input array nums as the one showed in the presentation example so we're going to have 1 12 negative 5 negative 6 50 and 3. and let's go ahead and add the indexes as well so we have index zero index one two three four and five and k is going to be the size of the subarrays that we need to calculate the averages for so if we were to call this function with these input parameters we'd arrive at this line here where we initialize our max value to negative infinity and the reason we're initializing it to negative infinity is because if all of the subarrays within our nums array have averages that are negative numbers we still want to figure out which one is the maximum and if we were to initialize this with a value like zero which would be the default value for an integer if all of the sub-arrays within nums had averages that were negative the value that would be returned would be zero which would be wrong so if we're using negative infinity even if the maximum average of the sub arrays within this nums array is something like negative 1 million it would still be considered greater than negative infinity so following the initialization of our max variable we would arrive at this for loop here which is just a standard for loop that's iterating through our nums input array and for each iteration of this for loop we're going to do the code here and i actually shouldn't have named this window some because it's kind of misleading because we're not even using the sliding window technique for this naive solution so i apologize for that please don't get confused we're not using the sliding window solution yet this is still the naive solution so this window sum is basically representative of the sum of a particular subarray within nums so just ignore the window part and then we'd arrive at this nested for loop here so let's consider that we are in the process of iterating through our input array nums so we'll say that we're currently at index 0 of this top level for loop and our window sum is currently set to zero so let's write that out as well we'll just call it ws and maybe that's an ugly ws did the best i could okay so we have our windowsum equal to zero and we're on the first iteration of this for loop which is index zero so then we'd arrive at this nested for loop here and this for loop is going to be the loop that we're using to iterate up until k because for each index of nums we want to iterate up until k so if we're at the zeroth index of nums we want to calculate the average for a sub array of size four so we want one two three four elements in our sub array so we want this to be our sub array so what this for loop is doing is we're using the variable j to iterate up until the size of k so we're essentially going to stop iterating when j becomes equal to k so j would start at zero then j would become one then j would become two and then j would become three and once j becomes four j is no longer less than k so we would no longer iterate and that would leave us with this sub array here so for each iteration of this inner for loop we're going to arrive at this line of code here and this line of code is just making sure that we don't try to calculate the average for a subarray that isn't within the range of this nums array so for example if we're at index 3 of this top level for loop iterating up until the size of k would bring us here which is out of range of this array and the program would panic so what this line of code here is going to do is it's going to preemptively check that the subarray will not exceed the indexes of the nums array and i'll explain how it's going to do that now so basically the length of nums is how many items that are in nums right so we have one two three four five six items in nums and then we subtract one from that length and that's going to leave us with the maximum index for the nums array so the highest index that we can query a value for within this nums array is going to be five and the highest index that we can query a value for any array is going to be the length of that array minus one because indexes are zero based so if the array has six items it's only going to go up to index five because it's going to start from zero so for this nums array in particular this expression here is always going to resolve to five so we can actually just write that here so we can kind of have a better understanding of what's happening and the next expression that we need to pay attention to is this one here so here i plus k minus 1 just means that whatever index we're on if we add k minus one to that index we'll get the maximum index for a sub array of size four so for example if we're on index one and we add k minus one to index 1 so if we add 3 to index 1 we're going to get index 4 and index 4 is the maximum index for this subarray of size 4. so we're checking if the index that we get as a result of calculating this expression is not greater than the maximum index of the nums array so for this inner for loop we're only going to continue to increment our j and add to our sub array sum if this expression here doesn't resolve to true because if this expression resolves to true then it means that we've reached a case like this one here where we're at index 3 and adding k minus 1 to index 3 would give us index 6 which is out of range this array only goes up to index 5. so if we won't exceed the length of our nums array when iterating up until k then we can start adding to our sum but if we will exceed the length of our nums array when iterating up until k then we're going to go down to these two lines of code here which essentially terminate both for loops and they do that by we're setting i equal to the length of nums and the condition for this for loop up here to run is while i is less than the length of nums so if i is equal to the length of nums this for loop would terminate and the same thing with this one we're setting j equal to k here and the condition for this for loop to run is while j is less than k so if j is equal to k this for loop will be terminated as well so let's just keep going here so we're at index zero our window sum is zero we're going to start this inner for loop we're going to arrive at this line here index 0 plus 3 and let's go ahead and write this in here as well k minus 1 is always going to be 3 for this input array so 0 plus 3 is not greater than 5 because 0 plus 3 is 3. so we're going to go ahead and add to our window sum the value at index i plus j and the reason we're doing the value at index i plus j is because if we're at index 0 and j is 0 as well we're going to take this value and then we're going to stay at index 0 for this top level loop right and then we're going to increment up for this inner loop right so this is going to become 1. so if we're at index 0 on our top level loop and we're at index 1 for our inner loop then 1 plus 0 is going to be equal to 1 so this is going to resolve to index 1 which is going to be this value and the same thing for when j becomes two if our top level index is zero and we add two to it the index here is going to become two so we're going to take this value and then lastly the same thing for when j becomes three if we're at index 0 here and we add 3 to our index 0 we're going to get index 3 which is going to be this value here and then that is our sub array and we won't reach this case but i'll explain it anyway if we're at index 3 for i you can see where things become problematic because if we're at index 3 and j also is at index 3 which would happen because this inner for loop is going to iterate until j is equal to k which is four but if it's less than k three is still less than k so if we were at index three and j was also at index three the resulting index here would be six and we would try to get the value at index six of nums but nums only goes up to index five so the program would panic because we're trying to access an index of the array that doesn't exist which is why we need this line of code up here i hope that makes sense this is the most difficult part of this function to understand so let's just continue to try and step through this so we're still at index 0 and then for our inner for loop we're at index 0 and this expression here isn't going to result isn't resulting to true when we're at index zero so we come down here and we're going to add nums i plus j so if i is zero and j is zero we're going to add nums at index zero so we're going to add one to our window sum so let's go ahead and erase that and change this to 1. and we're not going to do this because of course this didn't resolve to true so we're going to go back to the top of our loop here and let's actually write out what indexes were on for these loops so for i we're now on index 0 and for j we just did index 0 so we're now on index 1 because j just incremented after we add it to our window sum here so for j we're at index one so once again we're going to add to our window sum i plus j so our i is zero and our j is one so i plus so zero plus one is 1 so we're going to add the value at this index here so 1 plus 12 is 13 so our new window sum is going to be 13 here and once again we're not going to need to do this so we'll arrive back at the top of our inner for loop here this is going to become 2 it's going to increment to 2 and once again we're going to add to our window sum i plus j so 0 plus 2 which is going to be index 2. so we're going to add the value at index 2 which is negative 5. so we can go ahead and erase this and the new value becomes 8 because 13 minus 5 is 8. and once again we'll end up back at the top of this inner for loop we will increment to three and then we're going to add i plus j to our window sum again so i is zero j is three so zero plus three is going to be this value here negative six so we're going to add negative six to our window sum which is going to leave us with two because we're subtracting six from eight so we're left with two and at this point when we get to the top up here and we increment our j to four that means that j is no longer less than k it's now equal to k because k is 4. so we're going to terminate this for loop and we're going to end up down here and down here we're just going to check if our window sum is 0 which it's not our window sum is 2. so if our windows sum is not 0 we're going to calculate our max and we're going to do that by taking whichever is greater our current max which is currently negative infinity or our window sum divided by k and k is 4 and our window sum is 2. so 2 divided by 4 is going to equal 0.5 so we're going to take whichever is greater 0.5 or max and 0.5 is definitely greater than negative infinity so our new max is going to become 0.5 so we can go ahead and write that out here max equals 0.5 it's no longer negative infinity and we can just erase this so once we have our new max we're still in this top level for loop here so we can go back up to this top level for loop and we're going to increment our i so our i is going to become one and our windows sum is going to go back to 0. and this inner for loop our j is also going to go back to 0 because it's going to reset and now we're going to check this again so is one plus three greater than the length of our nums array minus one so is four greater than five no it is not so we can go ahead and start adding to our window sum so let's go ahead and move this as well because we're on index 1 now and we're going to add the value at index i plus j so 1 plus j which is 0 so we're going to add the value at index 1. so this is going to become 12 and we're not going to do this we're going to end up back at the top and we'll increment this inner for loop again and once again we're going to end up here so we're going to add the value at index i plus j to window sum so we're at index one of our top level for loop plus we're at index one of j as well so we're going to have an index of two and we're going to add the value at index two which is negative five so twelve plus negative five or twelve minus five is just going to be seven and once again we won't do this and we'll be back at the top here and this will become two and then we'll add i plus j to windows sum once again so 1 plus 2 is going to be 3 so we're going to add this negative 6 to our window sum which is going to leave us with 1. and we won't do this and we'll end up back at the top here and j is incremented to three and then we add the value at i plus j i is one plus three is 4 so at index 4 we're going to take the value 50 and add it to our window sum and that's going to leave us with 51 and we won't do this and we'll end up back here and j is going to become 4 and once j becomes 4 we're going to terminate this loop because this loop only runs if j is less than k which is 4. so we'll just go ahead and erase that and it's 4 now so this loop gets terminated so we end up down here window sums 51 so it's not zero so we're going to calculate our max so we're going to compare the max 0.5 with our window sum divided by k so 51 divided by k or sorry 51 divided by 4 because k is 4 and that's going to come out to 12.75 and 12.75 is greater than our current maximum of 0.5 so we're going to replace this current maximum with 12.75 and then once again we move up to the top of our for loop here and our i is now going to be equal to two so let's erase this and let's add the dot back there let's also erase this and move it up to two and we can also erase this so our window sum is going to go back to zero and again i apologize for calling this windowsum i just want to reiterate that we're not yet using the sliding window pattern so once again we're going to arrive at this inner for loop and it will have reset so this is going to be 0 and then once again we're going to arrive here and our i is two plus three is five is five greater than five no it's not so we're still going to start adding the subarray values to our window sum starting with i plus j which is two plus zero which is going to be index two so we're going to start by adding negative five to window sum which makes windows sum negative five and then back to the top of the loop here we increment j so j is now one and once again we end up here so two plus one is index three the value at index three is negative six so we'll add negative six to our window sum which is going to leave us with negative eleven and once again we get back up to the top of the loop and we increment j so j is now 2 and we'll end up here so 2 plus 2 is index 4 and the value at index 4 is 50. so we'll add 50 so we'll add 50 to our windowsum which leaves us with 39. then back to the top once again increment our j to three and we'll end up here again two plus three is going to give us index five and index five has a value of three which we add to our window sum as well which gives us 42 and then back to the top of this inner for loop we increment j j becomes 4 j is no longer less than k it's now equal to k so we're done with this inner for loop we'll end up back down here once again and our current max is 12.75 so we're comparing 12.75 with our window size divided by k our window size is 42 k is 4. 42 divided by 4 is 10.5 12.75 is still greater than 10.5 so our max will remain the same and then once again we will end up at our top level for loop and our i will increment to three and our window sum goes back to zero and we end up back at the top of our inner for loop and j is going to go back to zero and then we arrive at this line of code once again so let's go ahead and move this as well this is going to be three now so three plus three is going to be equal to 6 which is greater than the length of nums minus 1. so 6 is greater than 5. so we're not going to do this code anymore so we're going to actually do this code here now so we're going to set our i equal to the length of nums so this is going to change to 6 because the length of nums is 6 1 2 3 4 5 6. and this for loop is only going to run if i is less than the length of nums so this for loop will be done and also we're going to set j equal to k j is currently zero we're going to change it to four and this inner for loop is only going to run while j is less than k while j is less than four but j is currently equal to four so this inner for loop will terminate as well and the last thing that we're going to do before leaving this top level for loop is we're going to check if windowsum is not equal to zero so if windows sum is not equal to zero we'll do this but windows sum is equal to zero now it's still zero so we're not going to do this code here and that means we leave this for loop here and we end up down here and if max is equal to negative infinity we'll return 0 but it's not max is equal to 12.75 so we're just going to return max so we're going to return 12.75 which will be the maximum average when considering all contiguous sub-arrays of size 4 within this nums array now let's briefly go over the time complexity of this particular implementation so if you've noticed for every index of nums so we'll say nums is our n so we have our big o of n so for every index of nums we have to iterate k elements as well so our time complexity is going to be o of n times k and what that's going to look like is it's going to look like this we have nums here and let's just put the indexes 0 1 2 3. 4 5. so for each one of these we iterated up until k elements so for example at 0 to get to the sub array of size 4 we started at this top level for loop at zero and then in this inner for loop we iterate up until k elements to calculate the average for a sub array of size four so at zero we touched index one two and three and at index one of nums we touched two three and four and at index two of nums we touched three four and five and even though beyond index two at index three we couldn't continue so we terminated things since this is big o we don't need to take those details into consideration so we can still consider this o of n times k and by n times k i mean n times k and when looking at this you can get an idea of the inefficiency by seeing the amount of times we process the same indexes so let's see if we can come up with a better solution to how to solve this problem so at this point i can now introduce you all to the sliding window solution so we now know that the naive solution is not ideal because we have to unnecessarily iterate through elements that we've already seen before when iterating through k for each element of nums the way that the sliding window solves an issue like this for this problem in particular is by instead of adding up the sum for every element of k again and again for each index of nums we keep track of the first sum that was calculated and just subtract the value that's at the starting index of the window and add the value at the index after the current end of the window this simulates moving the window up for this to work we will need to keep track of two indexes the index at the start of our window and the index at the end of our window from there it's just a matter of calculating the average for the window and then just incrementing the start and end indexes and updating our sum variable so let's take some time to code up the algorithm to make this work okay so we are now back in our youtube patterns directory and just to reduce the amount of typing that needs to be done i'm just going to go ahead and copy all of the code from our naive solution into a new file that we'll just call max average sub array i and now we should have a new file that we can open up that contains all the contents of the bad max average subarray file and the reason we're doing this is because we still want to keep this main function the only thing that we are going to change actually is the function for find max average so we can go ahead and just delete everything inside of this function and since our naive solution is part of the same package we're going to have to actually rename this function so we can name this function find max average sliding window and we're going to have to go ahead and do the same thing here and other than that everything else is the same we're still going to have the same input parameters and we're still going to print our answer here so now we can just start writing the algorithm for the sliding window solution within this function so of course we're going to start with a variable for our windows sum which is going to be an int and we will also create a variable for our start which is going to be the start of our window which is also going to be an int and we're going to initialize our max as negative infinity just like before and from here we're just going to simply create a for loop and the variable that we're going to use for the index of this for loop is going to be end because this is going to be representative of the end of our window so we're going to start it at 0 and while end is less than the length of nums we're going to increment end and within this for loop the very first thing that we're going to do is we're going to add to our window sum the value at end in our nums array so essentially what this is doing is our end starts at the first index of the nums array so our end would start here at eight eight six zero and we basically just want to add each value at each index up until we reach the subarray size of k or the window size of k so once we get to this point we want to stop adding the values to our window sum because at that point we already have our window size or sub array size of k and the way that we're going to stop it once we reach the window size is we're going to do if end minus start plus 1 equals k then we will calculate average for the window and all this is doing this in minus start plus one is getting the current window size so we can get the window size by subtracting start from our end and then adding one and i will go over how that's working once we get to the point where we try to visualize this code so once we get to the point where our window sum is the sum of all of the elements within window size k we're going to go ahead and calculate our max and we're going to do that by doing math.max just like before and we're going to compare the max the current max with the float 64 windows sum divided by load 64 k just like before and once we calculate the average for this window this current window that we're on we want to move on to the next window because we're done with this window at this point so that's when we're going to subtract from our current window sum the value at the start of our window and then we're going to increment our start just like in the illustration and we're going to keep doing this until we reach the end of the array and by that time our max should be the maximum average for all contiguous sub-arrays of size four so we'll just return our max so let's go ahead and save this and see if it's working as expected we can clear and then we'll go run max average subarray i dot go actually i'm sorry i'm using the wrong input array for this so and also i forgot that this is part of the same package as our last solution so we're redeclaring the funk main as our entry point in this one as well let's go back into this old one you know what i'm just going to comment this out and back into max average sub array and let's just go back to the problem online and take this and put it back in our nums array and change this to four i'm sorry about that i'm not sure when i actually tested out that other input but in your file in your bad max average subarray.go file these inputs for you should still be four and the input array from the actual problem example at some point i was testing out another input i just don't remember when so let's go back into here so our main function should have k equal to 4 and it should have nums equal to this array of integers from the example of the leak code problem so let's go ahead and clear this and then go run max average subarray.go and as expected we get 12.75 same as the old solution the naive solution so now let's take some time to go over this code okay so let's take some time to go over this code so we'll start by writing out our nums input and we're going to use the same input as with our naive solution and k will be 4 still and we're going to start with our window sum being equal to zero and our starting index is going to be equal to zero as well and remember for this solution to work we need to keep track of both the start of our window and the end of our window and our max is once again going to be set equal to negative infinity for the same reasons as explained before and we're going to simply arrive at this for loop here and we're going to refer to every index of this for loop as our end so as we're iterating through this array every iteration is going to be the end of our window so our end will start here and then it'll move here and then it'll move here and then here and so on and so forth so we will start at index 0 and build our window up to the size k so we'll arrive at this line here where we're going to add to our window sum the value at end so let's go ahead and play this out so we'll start at this for loop our end is going to be zero in the beginning and our start is also going to be zero so we'll just have zero for start our window sum is going to be zero as well so we start here at index zero so we're starting here and we're going to add the value at this index to our window sum so we'll add one to the window sum so window sum plus one and once we add this value to our window sum we're going to end up here and it's going to check to see if our window size this here calculates our window size our current window size is equal to k yet and if our current window size is not yet equal to k then we're not going to do this code we're just going to continue back up to the top of the for loop and continue to add the values at the indexes and we can see that end minus start plus 1 gives us our current window size because our current end is 0 and our current start is zero so zero minus zero zero plus one gives us a window size of one and the same would be true if our end were here and our start were here we would do index two minus index 0 plus 1 which would be 3 which would be the size of that window so as you can see this little formula here calculates our current window size based on our start and our end so the reason we're not doing any code in here until our window size equals k is because of course we want to calculate the maximum average for window size of k so until we get to the window size of k we don't want to calculate the average we just want to keep adding the value to our window sum so that's why here we're at index 0 we add the value 1 to our window sum and we don't do this code we just move back up to the top of the for loop and now we're at index one and once again we're going to add the value at our end our current end is one so we're going to add 12 to our window sum and once again our current window size is not equal to k because our current end let's actually just write this out so this is our end and this is our current start because as you can see here we haven't done anything with our start yet so it's still zero and our end is moving up as we increment our for loop and we have not yet reached our desired window size because our current window size is only two elements because end minus start so one minus zero plus one is two so our window size currently a size two but we want a window size of four right so we're not going to do this again we're going to end up back at the top of our loop and we're going to move our end up from one to two index two so we can erase our end here and our end is now here and once again we'll add the value at our end to our window sum so the value is negative five we'll add it to our window sum so we'll do plus negative five and once again we'll check to see if our window size is the size of k it's not our window size is three so we're going to skip this code again move back to the top of the loop and increment our end once again so our end is now index three and we'll add the value at our end to our windows sum so we'll add negative 6 to our windowsum and at this point we're going to arrive here and our window size is equal to k now because end minus start so our end is index three and our start is index zero so three minus zero is three plus 1 equals 4 which is our value for k which is the desired window size and if you see we have 1 2 3 4 elements between our start and end so that means we'll go into this code to calculate the average and to calculate the average we're just going to simply divide our window sum by k by four so our current window sum let's go ahead and resolve this so zero plus one plus twelve minus five minus six is going to equal 2. so let's erase this and go ahead and write 2. so our current window sum is 2. so we're going to divide 2 by k which is 4 so we're going to divide 2 by 4 which is going to be 0.5 and our current max is negative infinity 0.5 is greater than negative infinity so our new max is going to become 0.5 and here just like in the illustration we're going to subtract the value at the start of our window so we're going to subtract 1 from our window sum and then we're going to increment our start so we'll subtract one and then we'll get one so our window sum is now one and we're going to move our start up one index and then we're going to go back to the top of our for loop here and we're also going to increment our end just like in our illustration so the end is going to move to 50. and just like in the illustration we're going to add to our windowsum the value at our end which is 50. so we're going to add 50 here to our window sum so plus 50 and actually let's just write this out as 51. so our window sum is now 51. and then we'll end up here again and at this point our window size is four again so one two three four so we can go ahead and once again go into the code here and this is no longer true so now we're going to take our window sum 51 and divided by 4. and that's going to be 12.75 and we're going to check which is greater our current max or 12.75 12.75 is greater than our current max of 0.5 so our current max is going to change to 12.75 so we can erase this this becomes 12.75 and we can erase that too and once again we're going to subtract the value at our start from our window sum so the value at start is 12 so we'll subtract it from our window sum so minus 12 equals 39 and then we're going to increment our start once again so our start is going to move up to index 2. and then we'll go back to the top of our for loop and we're going to increment our end as well and we'll add the value at our end to our windows sum so 39 plus the value at our end which is 3 39 plus 3 is going to be 42 so our new window sum will be 42 and our window size is equal to k4 so we're once again going to calculate our max so our current window sum is 42 so 42 divided by 4 equals 10.5 and our current max is 12.75 which is greater than 10.5 so we're going to leave our max as 12.75 and we can erase this and once again we'll subtract our start value from our windows sum so we'll subtract 5 from our windowsum and we'll get 37 then we'll go and increment our start and then we'll head back to the top of our for loop here and at this point our end is no longer less than the length of nums so we're not going to do anything else in this for loop so we'll go down to this return max here and our max is 12.75 which is what will get returned now as you can see with this solution we didn't need to unnecessarily iterate through indexes that we already iterated through so instead of our solution being o of n times k this solution is actually big o of n and the reason for that is because this for loop is going to iterate through every element of n right so that's o of in right because it's going to scale linearly with the size of n but then also we have this start as well and our start isn't going to touch every element of in it's essentially going to touch every element of n minus the window size so it's going to look something like this so we have of in plus in so let's imagine that this in is our end here that touches every single element of our nums array right and then we have our start here that also touches almost every element of our nums array but it's not going to touch in elements it's going to touch something like n minus k minus two elements somewhere around there so if our start only gets to index three that means it's only touching four out of six elements there are six elements in this array so our n is six here but our start only touches four of them so if we go ahead and plug these numbers in here we'll get six plus six minus four minus two four minus two is two so six minus two six minus two is four plus this six we'll bring it down and then this is going to equal ten so our end touches one two three four five six elements and then our start touches seven 8 9 10 elements so if we were to just write it out you will kind of see what i mean by this n minus k minus 2. but of course since this is big o we ignore constants so we actually don't even need to consider any of this because they're all constant so we really only need to pay attention to o of n so the complexity is big o of n which is a pretty substantial improvement from our naive solution so that is going to be it for my explanation of the fixed window size variant of the sliding window pattern in the next video we're going to continue with the sliding window pattern this time using an example of a dynamically sized window variant of the sliding window pattern and although this initial explanation used a leak code problem that isn't in delete code patterns list the following videos for the sliding window pattern are going to be explanations of problems that are actually in the leak code patterns list anyways i hope this video was informative and please don't forget to like and subscribe if you aren't already subscribed and i'll see you in the next one

Channel: selikapro

Views: 1,095

Keywords: algorithms, sliding, window, technique, arrays, strings, linkedlist, maximum subarray problem, programming interview, coding, array data structure, computer programming (professional field), yt:cc=on, software, interview, technology

Id: XfSgQvKfcys

Length: 55min 37sec (3337 seconds)

Published: Fri Aug 06 2021