House Robber IV - Leetcode 2560 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem House robber 4 if you haven't solved the first three House robber problems I would definitely recommend at least solving the first one I think we've solved one two and three on this channel or the other neat code Channel this problem will definitely be similar but uh definitely different almost like they're trying to like trick us with this question but let's get into it the idea is that we're going to be given an array of integers so in this example we're given something that looks like this like with most of the House robber problems the idea is that each of these numbers represents a house we are trying to rob some of these houses they give us a parameter K in this example it is equal to two so that means we're trying to rob at least K houses so at minimum K houses we want to Rob so in this case two of them now even though they tell us we're robbing a minimum of K houses after you go through the entire description it becomes pretty clear that you would probably never want to Rob more than K houses in the first place so you can pretty much just assume that we're robbing K houses now why do I know that let me just kind of spoil it for you just like go through the rest of this problem description we want to Rob at least K houses so from here we want to Rob K of them we do not want to steal from adjacent houses so if we take this we cannot take that so then we' maybe take something like this okay so in this case we've taken exactly two houses and among these K houses among all of them we want to take the maximum number among all of these so they tell us that uh over here they say the capability so that's the key word that they use here is the maximum amount of money that we steal from one of all of the houses that we robbed from so aka the maximum among the ones that we actually robbed from so now you tell me if we've taken from K houses and so this is what we have ADD additional houses is never going to make that maximum number any smaller right at the very least you should agree with me on that so if there is a solution and there's a solution where we rob exactly K houses and there's guaranteed to be a way to rob that many so we'll always know that there at least will be a solution and so if there is a solution then adding more houses to it adding like a third house more than we actually need more than K is never going to help so we don't need to do that so that's why we can assume that we're only going to take exactly K houses not at minimum K houses so anyways that was kind of a tangent but I want you to know that those sorts of tangents are very important in solving problems like these I call it making observations about the problem it's very important don't try to skip this step so let's get into this with the main idea out of the way like what this problem is asking for it seems pretty difficult because there's so many different ways to rob houses it's more than just n squ because n squ would mean like the contiguous subarrays from each element but with this we can either choose to rob a house or choose to skip a house so we have that choice for every single element so we're going to end up with something like a decision tree where we can choose to or skip to choose three or skip three and we kind of just keep going like that choose five or skip five and then among each of these paths it will tell us how much we could Rob so for a given path this is one possibility among all of these values we will take the maximum which in this case is five and then we'd say okay for this path where we robbed at least K houses five was the maximum and maybe for a different path uh something else was the maximum among all of those paths and obviously this would have been an invalid path because we cannot take contiguous houses so three is technically invalid so sorry about that if that was confusing um but this was mainly just to illustrate the main idea among all of these different paths we want to get the one that has the minimum capability so if you take the maximum from this group maximum from that and for every path you want to get the one that has the minimum and for this example the minimum is going to be the one that has this one and this one because if you look at this group the maximum of this group is going to be five if you take any other group that has at least K houses in it if you take this and this one it has nine as the maximum if you take two and three three it has three as the maximum so you might think that this is better but this is technically invalid CU we cannot have two houses that are adjacent to each other so for that reason we cannot take this and so some other possibilities I guess is this and this but again that also has nine so I think we pretty much went through all of the valid possibilities at least so among all of those five was the smallest so the solution I showed earlier is going to be exponential 2 the Power of n but we can use caching the memorization strategy to get that down to actually be an N squ solution I'll quickly show you the code for that but this solution actually gets memory limit exceeded because it's not uh very efficient not just in terms of time but the space complexity is also n^ s we can get that down by doing a bottom up solution but the bottom up solution will give us time limit exceeded because even though the memory is going to be link here the space is going to be inefficient so we're actually going to need a better solution than the one that involves dynamic programming the good thing is is that that solution is actually easier I'll show you that one in just a couple minutes so very quickly let me show you the memory limit exceeded solution so there might be some spoilers here but uh this is the full recursive solution I added a cashing to it I had a couple simple base cases and then just the choose and not choose a recursive steps and then just minimizing that and then returning it and then the bottom up solution which is this code right above it here is very very similar to the top down code I won't go like super in depth and draw this part out just because it's pretty complicated and there is a more efficient solution that is also easier that I'm going to show you now so I feel like I'm obligated to mention that if you're not familiar with binary search if you're not familiar with neat code definitely check this out link will be below and definitely solve either one of these two problems Coco eating bananas or capacity to ship packages CU they're very similar to the trick that I'm about to show you right now and I would probably recommend Coco eating bananas you can see the solution here in pretty much every language and video explanation as well so just to tell you what the trick here is it is binary search I think you're probably wondering like if you haven't seen some of the more recent videos or just any video related to Coco eating bananas you're probably wondering how that's possible more importantly how would you be able to know that this is a binary search problem and not a dynamic programming problem like we talked about earlier well first of all it is a dynamic programming problem so if that's like your solution there's nothing wrong with that there's nothing wrong with determining that this is an N squ problem using dynamic programming for problems like these it's very hard to arrive at the slightly more optimal solution which is in this case I think going to be n log M so in some ways it's not even 100% true that this is always going to be more efficient in most cases it definitely is but yeah it's hard to come up with these slightly more efficient Solutions when you're not really sure and I'm sure you're wondering like how would you be able to come up with this by yourself that's a very hard question to answer I think I probably wouldn't really try to if I were you just focus on learning the pattern and being able to apply it when you need to in the future but with all that out of the way let's think about how we can apply binary search to a problem like this one the general idea is that first of all obviously we're not actually searching a data structure here we're not searching for some kind of Target we're not doing anything like that so the way we apply binary search for problems like these I call it searching on a range in my algorithms for beginners course I have that pattern over here under binary search there's searching an array and there's also this concept of searching a range of values and so I'm basically just going to kind of take you through the process of breaking down a problem like this one first we want to uh do binary search on a problem like this one the general idea is that you can take something like this problem where there is like a step that involves brute forcing something and we can optimize it by applying binary search so I'll abbreviate that with BS and we do that on a range of values and usually that range is the part that was inefficient here so it's kind of like a three-step thing you find like The Brute Force thing you opt optimize it by applying binary search I don't know if it's actually three different steps but this is how I kind of think of it so for a problem like this one it's kind of hard to apply this we don't even know what our range is well what we're trying to do is find something we want to return the minimum capability so probably that's what we're trying to find the answer to what is the capability the minimum one so now I'm thinking of that range already in some ways I guess I'm kind of skipping these steps but I know that for my capability the smallest the capability could probably be is one it's probably never going to be less than that and usually the setup of this is pretty easy for one of these end points usually the smaller one is going to be one now what's the bigger end point of this going to be what's the largest the capability could possibly be for this problem it's not super uh complicated but it's a little bit subtle it's not something that's going to be obviously clear to you unless you actually think about it well what is the capability again that is the maximum amount the robber can steal among all of the houses that they actually chose to steal from so the maximum that the capability could possibly be is whatever the maximum value is in that array of nums it can never be bigger than that so here we can just say that our range is going to be uh from one to the max of nums so this is the range that we're searching for so now we have the range at least and now I guess we're going to do these other two steps figure out how we would solve something like this in a Brute Force way and then in terms of optimizing it it's pretty straightforward it will just take that Brute Force approach and instead apply binary search to it what I mean is that you we now have this range of values to search from we could do it in linear order from one to two to three all the way up until the max number and we'll stop at whichever one was the largest one that uh or I guess in this case it's the opposite we're actually going to stop at the smallest one that is valid but once we do have that stopping point we're pretty much done now rather than going through those one by one I guess in this case we'd be doing it in reverse order instead of doing that we are going to run binary search on this range of values so now in terms of what's left for us to do here well let's think about this if somebody gave me some capability let's call it C and they gave me this array and this input data how would I determine let's have an example for C actually let's do a dry run at this point so here is my example and so let's do our setup so our range initially is going to be from 1 up until the max number which in this case is nine so this is our search space and then we're going to run binary search here so let's calculate the Midway point and as I do this you'll probably get an idea of what the brute force and the optimal thing is so my Midway point is going to be uh five in this case and so that's my capability to put it into context this means that for example here if I took this and this I took took K houses from here and the maximum amount was five thus the capability here was five now if I took let's say uh just this house three and maybe there was another house over here that's two so therefore I did take two houses and the maximum one was three so that three technically in this case which is the max is also less than five and so five would also be valid in this case technically even though a more precise value is three we would also say that a capability of five is technically still valid and how can we now given a capability how can we determine if there are at least K houses in there that are not adjacent to each other it seems more difficult than it actually is believe it or not what I'm saying is given some arbitrary M value some capability how could we know if there are at least K houses from the input that we can choose from where the values of each of those houses is less than or equal to this value how could we know that well there's not a way to do it in constant time I'll just tell you that the way to do it is to do it in linear time and it's actually pretty easy all you do is scan through the input and count how many of the values are less than or equal to the capability in this case which is five well now is the part where I'm sure you're noticing well there's a potential issue with this counting and it's that it does not take into account that we're not looking at the adjacent neighboring houses we do not want to include those because in this example what we would get is we'd count the two and we'd count the three and we'd count the five because that's also less than our capability we would not count the nine we would skip that but in total we counted three houses but the reality is we only needed two of them but we counted three and with these three we wouldn't actually be able to choose all three of them so that's why that this is an issue a very a simple example to show this would be something like this down here where maybe I have like a 10 and a 10 that are adjacent to each other the M value I'm looking at it might be a 10 and maybe my K is two so I'm looking for two values that are less than or equal to 10 and if I were to scan through this I would count two of them I'd count this one and I'd count this one as well but I don't actually have two I can only pick one of these cuz I can't pick the one that's adjacent to it so that's the issue just to make it very clear well the fix for this is honestly very easy it's almost too easy so if you weren't able to come up with it that's probably why think of it like this imagine if you just have like a line here anytime you see like a box like that's what we're trying to do we're getting a box and if we see one then we jump two SP spaces and if we don't see one then we just jump one space and we just kind of keep going and if we see maybe two adjacent boxes that's okay when we see the first one we take two jumps so we would go over there now maybe there's a box here that's good if there's not that's fine as well because this jump just means that we skipped the one over here so to like put it in terms of x's and o's maybe is better if we just have a bunch of x's and let's say we're trying to count all of the X's that aren't adjacent like for example here we could count this one and this one and that's what we're trying to do we canot count like two adjacent ones of these the algorithm is basically to pick one and then jump two spots Now We're Here jump two spots we're here we didn't pick anything so we can jump one spot we're here so we take that we jump one spot here uh and kind of just keep going so we counted one two 3 X's basically when we were here we saw that if we want to take this we want to count this we are not allowed to count the next one and that's the only restriction we can count anything that comes after that so that's basically the idea behind this algorithm so for us to be given some arbitrary capability and to determine if it's valid or not all we have to do is scan through the input array and then count the values comparing each to that capability itself and then if our count at the end is greater than or equal to k then we know that this was valid and we can try to look for an even bigger one so to briefly finish up the dry run we saw that five was valid so our range was 1 n we will now up our range to be 6 to 9 we would increase the lower bound of the range and now we're going to try a value that's in the middle of this 6 + 9 / 2 is 7 so now we would try seven we would count how many of these are less than or equal to seven so getting rid of this we go through all of these and we see only this one is bigger than or equal to seven so we only counted one but we wanted at least two so thus nine or Sorry Seven was too big so we're going to make our range smaller Now by taking the big number nine and decreasing it to be 7 minus 1 so it would be six and so now our range is just six and we would find that six is also not valid so the largest value that we found in the range 1-9 that was valid is five so that's what we would return here so the time complexity of this is going to be n because we're going to have to scan through the input every step of the binary search and log of M because if you remember our range the size of that is going to be determined by the max value in the input so that's what my M here is this is going to be the overall time complexity I believe the space complexity should be constant so I'm going to do pretty much a textbook binary search the way I like to code it at least so even though I said earlier that are range was going to be one up to the maximum of nums I guess a tighter way to do this would be to take the minimum of the nums as well for our lower bound I kind of overlooked that when I was talking about it earlier but we wouldn't expect us to Rob less than the minimum house amount so I think that's why we can do this as well and then we pretty much just do binary search while left is less than or equal to right we expect to return within this function and we expect that there to be a helper function let's just call it um is valid and it will be given some capability and we will determine if that capability is valid for the input or not so assuming we have a function like that this becomes very trivial kind of just show it to you we can calculate the Midway point so mid is going to be left plus right divided two we don't really worry about overflows for this but we could if we wanted to and we also uh will have our function being called basically so it's going to be pretty easy from here so if is valid given that value M for the capability if it is valid then we will update our result uh to be that value and then we can update our right pointer uh to be equal actually this makes me realize I might have misspoken when I was doing the drawing explanation so sorry about that I keep forgetting we're trying to return the minimum capability so every time we determine that this is valid we are actually now looking for a smaller valid result so we should actually shrink our range so we should take our right pointer and set it to be mid minus one and in the opposite case we can set our left pointer to be mid plus one because if we find that this is not valid then we will have to try a bigger capability to see if that's valid and then at the end we will return the result which I have yet to declare so let me do that somewhere and we expect that the is valid should become true at least once so this should execute and result should be reassigned at least once the last time it's reassigned should be closest to the result so our is valid function now at this point I'm just going to have a a pointer I and then I'm going to have our count which is zero initially and we'll say while I is in bounds we're going to check is this number less than or equal to the capability that was passed into us if it was we can increment I by two and increment the count by one otherwise we will just increment the pointer by one and at the end well I guess inside the loop we could check if the count ever equal K we could do an early break out of here and then at the end we can just return whether the count is actually equal to K or not so this is the helper function where most of the logic went into but you can see that this function itself is pretty easy pretty simple once you know what to do but assuming the rest of this code is correct uh yep you can see here that the code does work it is pretty efficient I can promise you that so if you just want to see it one more time here you go but yeah this is very much not easy to come up with if this is your first time seeing this trick this binary search trick on a problem like this one it is expected that it's going to blow your mind it definitely blew mine the first time I saw it but thanks for watching check out n code. for more and I'll see you soon