Filling Bookcase Shelves - Leetcode 1105 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so it's getting to the end of the month so you can expect me to be a little bit triggered in this video but I'm going to make this problem Look So Easy you're not going to believe it filling bookcase shelves so before I even get into kind of you know the poorly worded description I wanted to look at some of these comments down here I saw a comment that said I thought this problem could be solved by greedy not a hard problem but very easy to fail in an interview if not careful and so it makes me realize oh this comment is 3 years old that was before the N code 150 existed because if you had gone through the N code 15 which is a list of you know pretty good problems I think that apply to a wide variety of other problems and if you went down I think that to a one onedimensional dynamic programming you'd see a problem coin change it's very similar to the problem that we're solving today it's so similar that it actually fits into a category of problems which you know I've done a some course stuff on it's the knapsack category of problems and this problem is very similar and that's the main reason I was able to solve it you know pretty easily so the idea is that we are given a book shelf so that shelf has a width and that is a parameter provided to us in this case that width is four so in a sense that's kind of like our napsack like container that's the max that our napsack could contain in a way right it's not directly uh comparable but it's similar it's analogous and we also have a bunch of books that's kind of like coins in the context of coin change each book though has two things it has a width and a height so the idea is that we are filling these books in the order that they appear so book number one is going to go first and quite frankly this description I'm just going to get rid of it to save a space okay that's much better the idea is we want to fill them in in this order 1 2 3 4 5 6 7 but it didn't have to be like this why didn't we just put um by the way this is the first shelf so like we have a shelf of width four here and then we decided to have a second shelf here the width is always going to be the same it's always going to be four but the height of this shelf is variable this shelf you can see is a height of three this shelf here is a height of one this last one is a height of Two And so when you add all of those up you get the total height and that's what we're trying to minimize we're trying to minimize this part and this is the way that we minimize it this is the correct solution the problem but imagine if we didn't do it that way imagine if we did this we have one and then we put two on the same shelf okay then that has a width of two so it'd be something like this and so now the height of this shelf is three and we can't uh fit this next book on the same shelf because we have a width of four and this one has a width of two so the width that we have remaining here is one obviously this one now has to go on the next shelf so if we do it this way you'll end up with something like this where now we have three and then maybe we fit all of these onto the next shelf or you know you could put two of them here I guess but it wouldn't really save you anything you could put four and five here and then you'd have to put um I think six here um and seven has a height of two so this way you'll see this is three this is three and this is two so in total that gave us a height of eight so literally this first example shows you that you can't be greedy for this problem when I say greedy I mean try to fit as many books as you can on the first shelf when you run out of with then go to the next shelf you can't do that in this problem just like you can't do that in the coin change problem so once you realize that and if you have a good understanding of the coin chain problem it becomes kind of clear that this problem possibly can be solved with backtracking but most likely we can optimize that backtracking with dynamic programming and then arrive at a very efficient solution so again that should be obvious if you have a very deep understanding um with the questions in the N code 150 list like I do so now it becomes a matter of figuring out how to kind of think of that decision tree what are the choices that we have because of course we're going to have like a pointer ey which tells us what the current book that we're at and so then one naive approach to take with the decision tree is to track the index ey and also Al to have a variable which tells us how much space we have remaining in the current um shelf that we're at obviously if that space were to reach zero or if we arrived at a book the book at index ey maybe has a width that is too great to fit on the Shelf then we'd have to then create another shelf and that's something again we'd have to keep track of and so of course the height of a particular shelf is going to be the max of heights of all the books that we placed on that shelf so that might be something you keep track of here or you know you might do that in the function itself but automatically you kind of recognize that this has multiple parameters if there were a way like when it comes to memorization with backtracking if there is a way to reduce the number of parameters we kind of always want to do that because we can always then optimize the space and also um sometimes the the me the time complexity as well but I'm going to show you that we can actually very much do that and it's very similar to what we did a couple days ago I think in one of the dynamic programming problems we only need a single parameter I I'll show you why that is because we are not like in terms of the decision tree we are going to think of it in terms of shelf by shelf not book by book like when we have a decision we're not thinking okay I'm going to put the book here or maybe I'm going to put the book next no we're thinking of it in terms of shelves so I'm going to say initially we start at index I equals z the choice is this I mean we have to put you know the one book right now we're we're at an empty shelf we have to put at least one book there the decision is if we put book one on the first shelf I I'll try to draw it out it might be kind of hard to do that then the choice is okay now start the next Shelf at index I equals 1 and the Shelf you know this is what the Shelf would look like the next choice would be well okay now start the next Shelf at I equals 2 that would be if we put one and this guy on the same shelf and then the third choice would be hey start it at I equals 3 that would be if we put this this and this on the same shelf but hold on a second that's invalid how do we know it's invalid well we're going to be doing something this as you can see we're having a variable number of branches this kind of indicates that we're going to have some kind of loop within our recursive function and that's exactly what I'm going to do and I'm going to keep track of two things I'm going to keep track of what the current width remaining is in the shelf so so as we loop from zero to whatever index that we stop at we're going to keep track of the current width the width starts at the parameter whatever shelf width is it started at four in this case every time we added a book we decremented from it so minus one okay here minus 2 we have a space of one left in uh this width so we're going to keep track of that that will tell us that okay we don't actually have enough space for this to be on the same shelf so that will tell us when we can stop so we'll have these recursive cases another thing we have to keep track of is among the books that we did place on the Shelf among all of those what was the max height of them because that's going to determine the height of the Shelf in this case we only had one so the max height was one um in this case we had this and this on the same shelf so the max height of course was three so we have to keep track of that and then with this Max height the sub problem becomes obviously the recursive case so um we already recognized that this one was invalid so I'll kind of continue the decision tree from here so here I equals 1 the choice would be okay now start the next Shelf at I equal 2 or I equals 3 in the context of this problem I equals 2 would basically say that this is by itself and then this guy is going to go on the next shelf I equal 3 would say that these two are together and then this one is going to be on the next shelf and we we can't really do ials 4 because we wouldn't be able to fit this on the same shelf so these are the only two choices um in this branch and so I'm just going to continue with uh this side because I know that's the correct answer but I want to show you how the recursive call like the return value of the recursive call is going to play into calculating the result because that's kind of what dynamic programming or memorization is all about it's called the recurrence relation so I want to kind of make that clear to you so here I equals 3 so for the record I equals 3 is the index so this was at index zero this was index one this was index two so three this is the book on this shelf this is the first book on this shelf so here obviously we could say I equal 4 I = 5 I = 6 and we can even say I equal 7 but 7 is an index that's out of bounds actually so this is the base case this is where we don't have any books and this is the case where we put all four of these books on the same shelf so that the next shelf would be at this index but that's out of bounds so this is the base case where we would return zero up to here and then from IAL 3 if we put all of these on the same shelf the max height of them was two so two is what would be returned up to this guy this guy put these two on the same shelf the height of that was three so we would take the two that was returned here and the three from here add those together and then return up to the parent five and then from here we only had a single uh book the height of that was one so add one to this five and that's how we got six so conceptually this might have seemed complicated but I bet when I show you the code it's going to be not too difficult and I'll analyze the time complexity there but I will tell you that this is actually the most optimal solution you don't need bottom up dynamic programming to arrive at the optimal solution for this problem okay so I'm going to create a recursive function called helper we're going to keep track of the current index that we're at the main base case remember was I equals length of books where we don't have any books remaining so the height of all of the shelves in that case is going to be zero and then we're going to start looping we're going to go for J in range starting at I up until the end of the books array but remember we might terminate out of this Loop early and I'll show you how we do that remember the two things we're keeping track of the current width which initially is always going to be the Shelf width because every time we start a recursive call we're going to assume that we're on a brand new shelf and it's going to be empty so this is the current width we're also going to keep track of what the max height happens to be among all of the books that we put on this shelf initially we'll say that that's zero we're also trying to minimize the total height the result I'm going to initialize to be very big Infinity in this case so now I'm going to get the current book and just for readability I'm going to do this so books I'm going to unpack it I'm going to get the width of the current book and the height of the current book and before we even try to place this book let's just make sure we have enough space for it let's check is the current width less than the width of the book like this is the space that we have left this is the width of the current book so sorry if this is confusing with the variable names but if this is the case we don't have enough space so at that point we have no choice but to break out of the loop otherwise we do have enough space so let's just try it out let's first update the current width by doing this um subtracting the width of the book and let's update the max height potentially by setting it to the max of what it currently is and the height of the current book now is for the recursive call and I guess I didn't explicitly talk about this in the drawing explanation but given that we're trying to minimize the height of the shelves it's in the context of the problem I'm sure you can guess that we're going to need a minimum somewhere in here and so we're going to try to minimize the result so take the minimum of itself and this is where we put the recursive call we're going to do helper so if we included the book J we're going to say this is the last book that we put on the current shelf so let's try starting the next Shelf at j+1 let's just try it but with this we have to add to it the height of the current shelf which is going to be the max height that we've seen so far so with this I'm going to add the max height and that's pretty much it so I'm going to zoom out a tiny bit we're going to need a bit more space here we're going to return the result that's pretty much it for the recursion down here we're going to call our helper function as you can imagine starting at index zero and that's what we're going to return the only thing is though we haven't really added caching to this yet but given that we only have a single parameter it's going to be pretty easy to do so I'm going to have a cache here which in my case is just going to be a hashmap here I'm going to say if I is in the cache we've already solved this sub problem before just return it and what exactly is the sub problem well it's telling us if we start a shelf from index I what's the minimum height it would take to fill the remaining books from the array and that's that's what's being cached here so um down here I guess we can replace the result with the cash value so cach of I will initially be this and then down here we can return cash ofi so that's pretty much the whole code it's about 24 lines actually I think we forgot to update result here and here so let's just make sure that we do that so I'm going to copy that here and I'm going to copy that here hopefully we didn't miss anything let me just confirm that this works and as you can see it does and it's pretty efficient this actually is the optimal time and space solution so let's quickly Analyze That firstly it's clear that this uh recursive function is going to be called n different times for like once for every book and once it's cached it won't be like repeated work or anything like that so what exactly is the time complexity of this Loop naive you might think it's also the length of the book so if that were to be n you might think that this is an N squared solution but let me tell you why we can get a more precise a Time complexity we can actually say that this is Big O of n time um whatever the Shelf width is let's call it w and the reason for that is we assume first of all every book is going to fit within the Shelf like any book is never going to be wider than a shelf width but at the same time every book is going to have a width of at least one so this Loop can't possibly run more than this many times because if every book has a width of one we will break out of the loop before we go through all the books right I think that makes intuitive sense and in most cases the books are going to have a width larger than just one so this Loop won't run end times it'll run this many times in the worst case so that's the time complexity space complexity you can probably tell is going to be o of n from the recursive call stack and also from the space that the cache is going to occupy I was mentioning that this solution might look complicated to you I'm not saying it's easy for sure especially if you're not familiar with coin change and some of the other dynamic programming problems I've talked about but let me just show you I mean first of all uh this is leak code's recursive solution I mean long explanation but maybe some people prefer that I don't know first of all their space complexity is not as good as mine and my God my God so it's about twice the length and it's about twice the complexity as well I mean look at all these variables that they're passing in I mean they didn't make it a nested function sure but the reason their space complexity is less efficient than mine is because you can see that their cache is actually two-dimensional mine is onedimensional because you know sometimes the people writing these leak code editorials are just not as good as you know some of us I'm sure many of you guys watching could probably write a better one than this and so then it comes down to the bottom up solution and thankfully the bottom up is actually very very trivial to come up with once you have the recursive solution let me show that to you right now we actually can at this point pretty much turn off our brains because now we've realized that the solution space is going to be um of size like proportional to the length of books so I'm going to say DP is going to be an array initially filled with all zeros of length books but I'm going to add a plus one just for the out of bounds case where I is equal to like the outof bounds index in that case we want return zero so that's why I'm doing the plus one here so now I'm just going to compute the result of the sub problems in reverse order I'm going to say for I in range starting at length of books minus one going in reverse order and then I'm pretty much going to turn off my brain at this point I'm sorry if you expected an explanation but I'm not going to do it I'm just going to copy and paste this because it's literally the exact same cuz now we're asking like we're trying to compute DP of I so instead of calling this cach of I I'm going to call it DP of I and DP of I is going to represent the same thing that it did in the recursive solution like starting at I if we had an empty shelf what is the minimum height it would take to fill the remaining books starting from index I so again we're going to have to keep track of the max height of that as well J is going to do the exact same thing we're going to get the width and height of that book we're going to check that we have enough space for it in the current shelf we're going to update the current width by subtracting the width of the book we're going to update the max height the exact same way this time we're just going to replace DP or Cache with DP same thing over here and helper of course we're not doing this recursively so what should helper be in this case yep you guessed it DP of J + 1 cuz that is the sub problem and I might be forgetting to do one or two things but remember that with our recursive function we were returning helper from zero and we're going to do the exact same thing here we're going to return DP from zero now there's no way to optimize the space to get it down to constant space because as you can see to compute DP ofi we're going to need potentially every single value that came after DP ofi so there's at least as far as I know no way to optimize the space but I think this is correct let's run it yep as you can see it works as you'd expect it's just as efficient in terms of time and space but you know some people prefer the bottom up approach it looks like it took us about less than 20 lines to do it if you found this helpful check out n code. I'm not joking when I tell you that 150 problem list will absolutely make you better especially if you can actually understand each solution and of course I have a bunch of courses that can teach you all this python stuff and also like the fundamentals of data structures and algorithms