Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)

Key Takeaways

what's good is that gonna be like blah blah blah Luis Luis say hola hola amigos should I edit that in so welcome back to the channel so as you can see today we're trying a different kind of setup because I'm trying to experiment and figure out what works so when I started this channel a lot of my videos were shot in like dark rooms and I just found whatever whiteboard I could find but what I want to try to do is try to improve the setup of these videos so as you can see there's kind of like a light on this video I just got like this LED light I also got a microphone so I'm not just speaking to the default camera audio so it's easier oh so it's easier to hear me with what I'm saying so I don't know if this video is going to turn out horrible and you won't be able to see any of what I'm writing this is kind of an experiment and I want to see what looks good and what is easier to consume as a learner so tell me below what you think about the setup we're trying anyway enough discussing these meta topics let's get straight into the question today okay so here is this problem simply put so what we have is a M by n matrix we have a matrix that is rows deep this many rows and this many columns let's just call it rows and calls that's the notation that I'm going to use from now on when we speak complexities when we talk about our approach to this problem and the brute force what I'm going to do is I'm going to step you through from the brute force all the way to our optimal solution and we will do an optimal solution walkthrough so the whole question this problem asks is in this rectangle in this matrix of numbers what is the rectangle with the largest sum in this big rectangle of numbers we have sub rectangles so here is a sub rectangle what I just drew is a sub rectangle and we have many of these sub rectangles in the matrix so the key to this problem is we want to find the sub rectangle with the largest sum here is another sub rectangle I want you to remember that a square is a special rectangle but not all rectangles are squares so this is a rectangle it just happens so that it's a square so we can have this we can have this our job is to find the rectangle with the maximum sum so how are we going to do this what I'm going to do is I'm going to walk you through all the approaches and the thought process as we solve this problem so let's walk straight into the brute force solution okay so now let us discuss the brute force solution so if someone asks me what is the largest sum rectangle in this rectangle and I'm sorry I forgot to show you what the actual answer is this rectangle this sub rectangle will be the answer for the largest sum rectangle in the matrix that rectangle you see right there which happens to be a square as well so that is the answer to this so what are we going to do to solve this problem so what we can do is a brute force solution where we explore every 2d rectangle so what is a rectangle made of a rectangle has a top left and a bottom right let me draw this out to describe to you okay so do you see that diagram right there we have a top left and we have a bottom right so what we can do is what we can do is we can select all the possible top left's and for when I say four it makes you think of a for loop for each of the top left corners we will try all of the bottom right corners let me make sense of this for you so what we're going to do is choose a planting let's plant a top left corner so do you see that L there the L signifies a top left corner now let me put a bottom right corner so you see that the top left and the bottom right sit in the same cell so this rectangle would be just that squared so what we do is we're going to advance this writes this bottom-right for each of the possible top left so we can choose so we chose a top left explore all of the bottom rights so let's just go through it quickly so keep an eye on the board and I'm going to advance the are the way our algorithm will do it so that is going to be our next iteration so let's iterate again so the next rectangle we explore is going to be like this and then what I do is I move my R again and now the rectangle we're exploring is like that I move my art again and again and we'll keep doing this until we get to the end so now we'd be inspecting the sum of the whole rectangle this whole way we'll remember the rectangle with the largest sum so what I'm going to do is I finished all the possible right points for the left planting I just chose so what is my job now my job is to try the next top left planting so let me do that right now so I've planted a left and we need to explore all the bottom rights so let's do that and again we advanced the right and then we advanced the right and again we advanced the right and notice how I only can go as far left as our left bound because we can't go negative in value we need to keep the rectangle over here because this is our top left and advanced on the right again and then keep advancing until we get to the end what we just did is we explored all the rectangles where this is the top left corner and what do we do now we advanced and try the next top-left corner and that's all we do I pick all of these are going to be top left corners every cell in the matrix is going to have a chance to be a top left corner so this is the brute force this is how we would explore every single rectangle in this 2d matrix so what is the problem with this so we recognize the problem when we start thinking about time complexities and we start trying to bound to the runtime so I want to ask you a question how many top left corners can I choose all of these cells are fair game for top left corners how many can I choose rows times columns I can choose that many top left corners so the number of top left corners I can choose is Rho times calls top left corners so for each of those top left corners that I can choose what is the maximum amount of work that I can do and this is now where my job is to provide an upper bound on the time it would take so let's think back to the worst case of the amount of bottom right corners we could explore so if I choose a top left right there the final bottom right corner I explore is going to be at the bottom right so how many bottom right corners am I going to try for all the possible top left corners so the upper bound this is where Big O helps us the upper bound on the amount of work we could do for these row x columns plantings is going to be the size of the matrix we see that that is the upper bound for trying bottom right points so let's keep note of that okay so now we have enough to derive a good bounding for the brute force solution so we know we're going to do row times columns top left plantings that's how many top left plant things we can do for each of those top left plantings what we can do is a maximum of Big O of Rho times columns work Big O is an upper bound we'll talk about Big O theta Omega and the different ways we can bound asymptotic complexities but what we need to understand is this gives us a good lower bound for the least amount of work it would take to even explore all 2d rectangles so what I do is I have to do row times columns left plantings for each of those the maximum work I do is going to be big off row times columns so imagine I plants are left here you see I'm not going to do row times columns work from this left because all my rights can be there but we will do a fractional component of Rho times columns and the fractional component will disappear and we are going to be upper bounded times columns so now I'm confident enough to provide a lower bound for the brute force so let's give ourselves a lower bound okay so what we can do now is we can provide a lower bound so this is big Omega again all addresses in another video but we're just giving a lower bound to the complexity of the leased work we're going to do so Big O gives us the upper bound we want to have a lower bound so the least work that I'm going to be doing is at least we have to explore all of the rectangles I'm not even worrying about getting the some of these 2d rectangles just to explore these rectangles we will do Rho squared times column squared work because we're going to be doing Rho times columns possible top left plantings and for each of those top left plantings we're going to be doing a maximum amount of work of Rho times columns upper bounded and that's why we use Big O there so this can be improved we can do better than this okay so what I'm going to do is I'm going to walk us through the optimal solution but I'm not just going to walk through it I'm going to explain exactly why we're doing what we're doing and how we could possibly get to this solution in an interview keep in mind this question is very hard this is not an easy question it is not trivial this is something you would have to struggle a lot and get hints for probably to solve it so if you haven't watched my video on contains algorithm and the max contiguous subarray sum problem then you should probably watch that before you watch this because we're going to use that but I'll show you why as we go so the way this algorithm works is we're going to have a left and right pointer so what we're going to do is we're going to play it to left and explore all the rights and then we advance the left and then we explore all the rights and then we advance the left and we explore all the rights so why are we doing this our job is to try every single possible left and right boundary of a possible maximum rectangle and what we're going to do first to initialize the algorithm is left and right start at the same place index 0 but what we're going to do is we're going to keep a running table of the sums of the row we're going to keep a running table of the row sums so what we're gonna do is we're gonna keep them in an array you will see why we're doing this in a little but let me just enter the values in this table so it's going to be zeros initially but we're going to enter all of these values into the running row sums table we would just add them in okay so left and right are sitting here and running row sums are this so what is my job so I'm going to be exploring all the possible left and right combinations of the possible maximum rectangle and my job is to find the best top and bottom bound at every single point in this iteration so when my left and right are here what does that mean I can have a rectangle going from here to here I can have a rectangle going from index here to here I can have a rectangle going from here to here and I just noticed these indexes are on let me fix them so we have four possible rectangles here that would look like this right so we can have this rectangle we could have this rectangle and then two more we could have this rectangle in this rectangle those are the possible rectangles if my left and right bounds are sitting right here so what is my job my job is going to be how do I pick the best top and bottom bound for this possible max rectangle with these left and right bounds so I look at this array and what I'm looking for is the maximum sum section so what algorithm can do that in linear time if we think back to what we already know we know our algorithms and we know contains algorithm can find the maximum contiguous sum subarray within an array in linear time so what is it linear with respect to it is linear with respect to the rows because what we're going to do is we're going to be doing this array will do contains on this and what you're going to see here is that the best maximum sum subarray is just the item six so what happens I come over here I set my new max rectangle values so my max rectangle left and right is going to be where my left and rights are sitting so it's going to be the index 0 for both the left and right ok so what is the top and bottom we just deduce that we deduced that the best top and bottom to choose is the maximum contiguous sub array of the running row sums and that is just the sub array sitting at index 0 so my top and bottom are going to be 0 what we know now is that if we choose a left and right bound of sitting right here the best rectangle that I can make looks like this it turns out that that is just a square but this is the best rectangle if I choose my left and right bounds to sit right here so our job is to explore all possible left and right bounds and then use contains algorithm to find the best top and bottom bounds at each left and right points so I think that was a lot of explanation but I think you can get it and we can confidently hop into this algorithm so let's advance through the algorithm slowly and again I'm sorry I forgot to put the maxim there the some of the region would be 6 as you can see it would be 6 so this is the best we've done so far planting at this left and right so what I do is I advance my right and now I need to update my running row sums so what I'm gonna do is all of these values on the right bound I'm gonna add them into the row summary so let's do that right now okay so now if I had the left and right bounds sitting right there what is the best top and bottom I could pick this is where contains kicks in and we're going to look for the max contiguous sub array some in this array what does that turn out to be so it turns out that the best I can do the max contiguous subarray sum is either going to be just right there or just right there the best contiguous subarray sum I can achieve is 1 so I either can choose this rectangle or this rectangle look at this this is very key I want you to notice something do you see how both of these rectangles have the same left and right bounds this is what we're investing and what we have is both of them have a region sum of one what is nine minus eight that's one what is six minus five that's one we could choose either of these so what we need to ask ourselves is if I choose these left and right points and this is the best that I could do does that beat the max rectangle sum that I've achieved you can see that it's a sum of 1 that does not be the best we have done which is 6 so that is not a winner so I continue on so now my job is to advance right I advance right forward so I just advance right forward and what do we need to do we need to change our running row sums we need to update that so let us update that okay so I just updated the running row sums for this left and right down so these are our left and right bounds we want to pick the best top and bottom bounds we run contains and we see the best we can do is sitting at index 2 this is the maximum continue separate just the item 1 so what would our max rectangle look like our potential max rectangle so do you see how we're trying all the left and right boundaries and we're using contains to choose the best top and bottom so what we're going to do is we're going to see does one eat the best I've done it does not be the best I've done so I continue on I'm just gonna continue on in my iteration this is not a winning rectangle so what I just did is I advanced right I advanced right forward and now I need to update my running row sums let's update our running row sums okay so what we just did is we just chose a new left and right bound we updated our running row sums and what we see is what is the best we can do what is the max contiguous subarray sum so we could choose the one the one is the best we will do for a top and bottom bound so at index 3 we're going to choose that as our top and bottom bound and we have our left and right so this is our candidate rectangle so does that rectangle with a sum of 1 as you can see as a sum of 1 does that be our best rectangle which has a sum of 6 it does not beat it so I advance in my iteration we will in advance our right pointer okay so what we just did is chose a new right bound it didn't work out the other ones so we advanced and now what we're going to do is we need to update our running row sums let's update our running rows ohms so this is the best we can do if I have a left and right bound and if I choose a top or bottom what is the best that I can do well I would just choose what's at index two so I see it's a negative two but a negative two of sum is not going to be our six so we've seen so far that we have not been able to beat our best rectangle which we achieved right there so what we do is we reach the end of our right bound so what we do is we advance the Left we set the right back to where the left is and we reset our running row sums and again this running row sums is we just add whatever is at the right bound into this running row sum so we have a running sum of what's in each row so what we're going to do is we're going to reset our bounds we've reset our bounds and we need to reset our running row sums because we have no running row sum we've done no iteration with this left bound so let's do that okay so what is my job right now my job is to add in the row where the right bounce it's the right bounce it's where the left bound sits so what I'm gonna do is I'm gonna add all of these into our running row sum so what I see here is I have this my left and right balance and I ask myself a question how do I find the best top and bottom do I brute-force it and do all these rectangles and get all the sums no I can keep the running row sums and do contains algorithm on it so what I'm going to do here is I'm gonna look at this what is the max sub array some region and it is the region from index 1 to index 3 so what is the sum of that region 16 and guess what we just beat 6 so we have a new winning rectangle what is that rectangle look like though I'd have to ask you that is what that rectangle looks like do you see how we chose a top and bottom bound based on the max continued sub array and our left and right sits there so that is our best rectangle let's update our bounds here so our max some is now 16 our left and right is where our left and right are which is index 1 what does our top and bottom become our top is the index 1 where our max contiguous subarray started our bottom is V 3 so 1 & 3 respectively so this is our new answer if a caller said I want an answer right now that's our answer so far so we need to continue with the iteration because we're not finished so we advanced the right pointer okay so we just advanced the right pointer I need to update my running row somes okay so I updated my running row somes so what is the maximum contiguous submarine so you can probably see it is going to be this 11 and 6 index 2 to index 3 what is the sum 17 do we have a winner yes we have a winner so what I do is I need to start updating my max rectangle my new best max is 17 my new best left and right are the left and right remember we're doing an exhaustive search of the left and right combinations so left is that one right is that index 2 so the top and bottom what is the max contiguous sub array of our running rose array it's going to be 2 for the top 3 for the bottom so that's it it turns out that this is what this rectangle looks like and if you remember back to the beginning this is actually our answer this is the best we're going to be able to do but I'm going to keep walking through this walk through just so you can internalize the algorithm and remember the code is in the description the code is always in the description for these problems so check the code out if you want to see more insight into this problem so what we're going to do is we're gonna advance the right pointer we will advance you forward okay so what is the maximum contiguous sub right here we see that the sub array if our left bound is at 1 and our right bound is 3 our max contiguous sub array turns out to be from index 1 2 3 and what does that rectangle look like it's that rectangle right there what is the sum of the region the sum is 16 do we have a winner we do not have a winner so I need to keep moving on I need to advance my right bound and keep searching okay we've advanced our right bound and what we need to do is we need to update our running Rossum so let's update that so what is the max contiguous subarray some well again it goes from one to three what is the sum of that region well let's look at what the rectangle looks like the sum of that region is going to be 14 we can see it from here if we do the arithmetic in her head we're going to see that the sum of the region with our left and right from 1 to 4 is going to be 14 is that a winner it is not it did not beat it and what we are going to do is our right has hit up against the end so guess what we try a new left bound what is the next left bound it sits right there what is the next right bound it's gonna stay where left is so I hope you're starting to get an idea of this algorithm and reset the running row sums to 0 because this is a new exploration of a new left bound again remember we trial left bound for each left bound I try all the right balance so reset the running row zones I could continue but this would probably take a really long time I just wanted you to understand what is really happening why are we using contains algorithm why are we iterating all these left and rights why are we trying all possible left and rights why are we doing contains algorithm to find all possible top and bottoms so is this the most intuitive thing it is not I spent an hour sitting here trying to solve this problem and it did not occur to me that we could do better than the brute force until I saw a video by two sharo I think this video is building on top of it because what I think too short did not address is the intuitions behind this problem and why do we do contains algorithm on the running row somes why do we explore all the left and rights we're compartmentalizing things to isolate the left and right X exploration and isolate finding an optimal top and bottom that is what this problem is about so what is the time and space complexity of this solution so let's look at the time first so I want to ask you how many left bounds can we we can choose a total of columns left bounds because the amount of left bounds we can choose is the amount of columns in the 2d matrix so we can choose columns left bounds so what is the maximum amount of work I'm going to do at every single planting of my column left bound well if I choose the first column how many columns can I go till I get to the end well I'm going to be able to go calls columns and then if I met index 1 I am going to go some fractional component of calls I will do a fractional work of calls that is my upper bound on the work for each of those plantings that we're going to do calls times so let me write that as an upper bound and for every single iteration how much work am i doing to find the top and the best bottom remember we're going to be doing contains algorithm on an array of size rows so it's going to be sized rows so therefore what we're going to be doing is o of rows work for each of these iterations so finally what does the final runtime become it becomes this so the upper bound on the amount of iterations we do is going to be call squared and for each of the iterations we're going to do we're going to be doing rows work big / O's work so our time complexity becomes hollow squared times rows this is the upper bound we put on the asymptotic behavior so what is the space complexity so the space complexity is as simple as Big O of Rose we're going to be keeping a running row sum matrix which has all of the running row sums for each row so Big O of Rose is going to be the space complexity for this problem so that is it the time is going to be Big O of columns squared times rows the space is going to be Big O of rows so that is the answer to these complexities for this question that is all for this question what we are trying to do here is we're trying to build one of the world's largest resource for software engineering interviews and this is for your study purposes these questions these problems I'm doing I already understand them this is for you to understand them and to help you be able to tackle these questions in a high-pressure situation that's why I'm all about the thought process and the understandings so anyway that is all for this video like this video if this was a clear explanation and you liked it subscribe to the channel and [Music]