Minimum Obstacle Removal to Reach Corner - Leetcode 2290 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today yes I'm still doing the daily problems for now at least uh we're solving minimum obstacle removal to reach corner I'm going to show you two solutions for this one the first one is the one I came up with in some ways it's actually a little bit more complicated but I think it's pretty easy to reason about I'd say that is a pretty good solution and then the second one is more optimal and it's actually so simple I'm actually mad at myself for not being able to come up with it because it's such a genius solution honestly I think regardless of how good you are at leak code I think you'll appreciate that second solution it's a real Beauty in my opinion and actually going from this solution to the second solution is such a small change we'll only need to change like a few lines of code the idea here is we're given a twodimensional grid it is a binary grid so ones are kind of these obstacles here and zeros are these free spaces that we have here so it's also guaranteed that the top left corner and the bottom right corner are going to be free and the reason for that is because this problem is asking us to determine what is the minimum number of obstacles it would take for us to reach uh the bottom right starting from the top left like how many obstacles would we have to go through what's the minimum I mean uh this second grid here by the way the reason these obstacles went away is because in the context of this problem they say that we can remove obstacles but that's really not not important we don't actually have to update the grid that's just kind of a distraction we can simplify the problem and just think of it in terms of how many obstacles do we actually have to go through and looking at this left grid here you can see there are multiple ways we could go down and then to the right and if you see it's these three obstacles we'd have to go through we could kind of go this way and again three obstacles but there are two ways we could do this that would mean two obstacles and go like that which would also mean two obstacles so the minimum number of obstacles to go through is two that's what we would return so multiple ways to solve the problem we know graph traversals are generally DFS or BFS those are kind of the simple ones if you approach it from a DFS perspective it's going to be inefficient because you're basically going to have to go through like every single possible path that you could reach the bottom right grid and that's going to require backtracking because at every single point there's going to be kind of a junction so like let me blow this image up by the way uh for example here we have two choices but we could have up to four choices at every step so here we have two choices uh like that we could go back up but there's no need to revisit the same position and then from here we have multiple choices up right down so we might visit the same position multiple times the maximum length of a path I guess in the worst case could be visiting every single position so in the theoretical worst case since we have like four branches every single time the height of that tree is going to be the size of the grid which is M * n that time complexity is going to be four the power of M * n not super efficient can we do better let's think about this for a second we want to know what is the minimum number of obstacles to reach this position thinking about the problem in Reverse or even just thinking about it in terms of sub problems for us to know the solution to that we probably want to reach this position and this position with the minimum number of obstacles if I want to solve this problem I have to kind of solve this problem and this problem too well I know the solution to this off the top of my head just kind of by looking at it it'll take at most or the minimum would be two obstacles to reach this here looks like no matter which way you do it you're going to have to go through three obstacles so this would be three so of course that's the minimum but how can we take this idea and Implement a code solution out of it because yes I need to know the minimum of these two but to know the minimum OB to reach these two then I have to kind of know the previous cells as well okay so now we're kind of realizing that what we want to do really what we want to do for this grid is for every single position figure out what is the minimum number of obstacles to reach that position so I'm still not sure do I want to do a DFS do I want to do a BFS do I want to use some kind of greedy algorithm I don't know I'm not going to try to force any of these algorithms into the solution I'm going to let the problem and the observations I make about the problem guide me to which one of these I want to use so let's continue to think about this for a second given that the top left is always empty it's always going to take zero obstacles to reach that position now from the two neighbors these are actually sub problems we can solve instantly because what's the minimum obstacles it's going to take to reach this position from here well either there's an obstacle here in which case that's going to be one or or this is free in which case it's going to be zero same thing with the one below it if it's free it'll be zero if it's not it'll be one and of course we are trying to avoid obstacles so among these two choices that we have which one should we pursue well there's a tie right we're looking at the frontier there's a cost of one to reach this and a cost of one to reach this so there's kind of a tie it doesn't matter which one we explore first so I guess I'll just pick this one so it took one to get here I know the blue on the black is kind of hard to read I'm sorry I think it's easier though to use this example drawing so now I'm here and now I'm going to look at my neighbors from here I'm looking down I'm looking to the right well how many obstacles is it going to take to reach this guy I'm not visiting this guy yet I'm just asking the question how many obstacles well it took me one obstacle to reach this and there's already an obstacle here as well so that's going to be one plus one which is going to get me here you might be seeing what algorithm this reminds you of and if you do you can probably just jump into the solution and code it up at this point but for the beginners I will continue going through this example so this is going to take two I haven't visited it yet this is also going to take two I haven't visited it yet but remember I still have a path down here I haven't explored yet this one is one so now among these three this one is two two and one which one do I pick the one that has the minimum obstacles to get there because I don't know necessarily maybe the path down here maybe there aren't obstacles down here maybe by just visiting this obstacle I can find a way to reach the bottom right after only going through one obstacle because these other two paths over here are going to require at least two obstacles so I'm trying to be greedy do you know of any greedy graph algorithms that can help you with this well even if you don't you can probably determine the solution to this because now you realize we're trying to determine the minimum of the frontier which data structure do you know can help us efficiently find the minimum a priority Q or a Min Heap just continuing to go through this example these are the cells we visited now it looks like our Frontier there's a two here a two here and a two here so it really doesn't matter which one we pick I'm actually going to pick this one because it's not the one that's going to lead us to the solution I'm going to show you that this algorithm is still going to work so I picked this one uh now my Frontier is over here uh this is this is three this is two and this is two so among these three which one do I pick the one that's the minimum well there's a tie between these two so it doesn't matter I'm going to pick this one over here and now my Frontier is three two and two over there which one of these is the minimum uh the tie between these two it doesn't matter I guess uh let's pick uh the one up here so I visited that one too so so far I know that the Min cost to reach all of these cells has been determined 0 1 2 1 2 two now my Frontier looks like this this is the three there's a two over here among these two which do I pick the minimum so it took two obstacles to reach this position now my Frontier is this and this the minimum is two so now I visited this position I reach the target I could continue going if I really wanted to know the minimum obstacles to reach this position over here but we could probably stop the algorithm at this point because we already determined the minimum for this position this is a greedy algorithm it is a variation of Dix's algorithm except we are not Computing the length of a path we're Computing the obstacles of a path that's the only difference so let me code this one up for you now given that we're only visiting each position at most once the time complexity will be M * n but each position could be added and removed from the Heap which is going to be in the worst case log of the size of the Heap we could in the worst case have like every cell added to the Heap so it will be M * n and even by the way if this term inside of the log was squared just so you guys know if you take this and you square it inside the log the way the log Works a log properties this two actually goes down here so you could move it like that and so now you can kind of see why even if the size of the Heap was squared it wouldn't actually affect the Big O runtime but it probably would affect like the Practical uh run time so let's code this one up and then I'll show you how to optimize it in a very clever way so first I like to get the number of rows and the number of columns and just put them into variables so let's get the length of the grid and then let's get the length of a row within the grid and then what I'm going to do is initialize my Min Heap like this I'm going to have a tuple inside of it because for each position what we want to use as the priority is the number of obstacles it took to reach that position but we also want to know the position itself so I'm going to add a tupal where the obstacles go first that will be used as the priority and then the position will go after so the first cell we want to add is the top left it takes us zero obstacles to reach that position and the coordinates are 0 0 and I don't want to visit multiple cells or rather the same cell multiple times so I'm going to have a hash set to basically prevent that and I will initialize that hash set with a single tupal which which is 0 0 what I'm doing here is creating a hashset passing in an array that just has one tupal inside of it that array of values is used to initialize this hashset so this is kind of a pretty common setup for a Dix's algorithm the rest of this is going to be nearly textbook Dix algorithm with a couple variations I have a unique style of doing this that really lends itself well to coding interviews if you are not familiar with Dias you can go to n Cod iio and I do have a lesson on the fundamental Advanced graph algorithms dxas is the first one I think this lesson will pretty much teach you everything you need to know about dxas has some nice little animations pictures code and you can even Implement dickes yourself this problem itself is actually free if you want to check it out you can do so and then Implement Dias and it has a solution in probably your language of choice but anyways back to the problem we are going to basically continue going while the Min Heap is nonempty we are actually guaranteed that we're going to be able to reach the bottom right position so within this Loop whenever we do we will return anyway I'm not going to put a return statement out here we could do that but it's never going to occur so I'm not going to do that um within the loop uh it's pretty textbook you take the Heap and you pop from it so Min Heap pop from it and we will get three values we'll get a tupal and we'll unpack that tupal in line this is why I like to have comments for what we're actually storing because it makes it pretty easy to reason about and now we have this before we go any further before we even ask what are the neighbors of this cell let's just check if we've reached the target is this tupal equal to the Target that we want the number of rows minus one and the number of colums minus one this is the bottom right corner if we've reached this return the minimum number of obstacles it took to reach that position if not we want to go through the neighbors let's use an array to do that it's a little bit easier and then we can Loop through the array so the neighbors are going to be row + one and row minus one and column + one and column minus one so now I have my four neighbors now I'm going to go through every neighbor neighbor row neighbor column in the list of neighbors I'm unpacking each of these lists as I go for this neighbor I want to add it to my Heap so that can then figure out which one of the neighbors has the minimum obstacles so I'm going to add to my Heap like this this Tuple well I'm going to add the coordinates of the neighbor I know for sure that how do I get the number of obstacles it would take to reach this position well how many obstacles did it take to reach the previous position so we have that obstacles over here and then we want to know is the grid position at this coordinate one if if it's one we want to plus one here if it's not one we want to do nothing we just want to you know say plus zero so a very easy way to code that is just to add the value at the grid column position uh not at the previous cell sorry this should be neighbor row and neighbor column and as soon as I add a value to the Heap I can then Mark it as visited even though I haven't popped it yet I already know there are not going to be any previous cells that could reach this coordinate with less obstacles because I'm doing this in a greedy way if there was a previous coordinate with less obstacles well that would have been popped instead but it doesn't exist so it can't be popped and therefore we can safely mark this guy as visited there won't be a path with less obstacles if that doesn't make sense to you you probably want to draw a picture you might want to watch that Dix's lesson I talked about earlier or you might want to do uh some self-studying that's the whole kind of point of greedy algorithms usually they can be explained with a simple proof by contradiction that's kind of what I was getting at when I explained that a second ago there's one other thing here the whole point of marking a position as visited is we don't want to add it to the Heap multiple times well this isn't going to guarantee that we're not really using visit anywhere this is where we want to use it if this neighbor row neighbor column is already in visit we can continue we will not execute these two lines of code but there's actually one other Edge case um we're going in four directions one of these directions or maybe multiple of them might take us out of bounds if that's the case we also do not want to get an index out of bounds error over here so let's add some code if that's the case or if the neighbor row is less than zero or neighbor column is less than zero whoops I should add an or here and change this to a zero or the neighbor column is too big meaning it would be equal to the number of columns you could also say greater than or equal but I think this is sufficient and lastly neighbor row is equal to the number of rows I could probably split this into multiple lines for readability but I think I will leave this as is I am pretty sure that is the entire solution it probably looks more simple than you expected I think this variation of dixes actually is more simple so let's go ahead and run it and now you can see it works it is pretty efficient time complexity wise this is O of n n * m log n * m but we can actually change this and make it this time complexity n * m you're probably wondering how that's possible it's actually easier than you think let's go back to the drawing board let's think about this for a second there is an algorithm that theoretically can find the shortest path in O of n * m time but usually there is a reason we don't do that algorithm it's called BFS and usually for shortest paths with edges that have weights we have to go with Dix's algorithm Which is less efficient and sometimes if you have negative weights you even have to go to a less efficient algorithm Bellman Ford but uh we're not going to discuss that but why can't we use BFS in this problem well let's actually think about this grid over here ignore the one to the left of it consider this grid we have this guy with regular BFS we'd have a q and to that Q we'd add the neighbors we would add this guy and this guy we'd say this guy takes zero obstacles to reach here and we'd say this guy takes one obstacle and so then we would just go through these in the order that we removed them like in my Q I'd have zero and I'd have the coordinates of that as well but I'm just kind of simplifying it with just the number of obstacles and I'd have one and then maybe I pop this guy first and I go through its neighbors okay takes me zero obstacles to reach here I add that guy and takes me one obstacle to reach here and I add that as well so I got done processing this guy and I added two more now I'm going to pop this guy which is this and I'm going to go down and say it took me two obstacles to reach here and two obstacles to reach there so this is where the problem is coming with BFS first of all if we really want to know what was the minimum for a position like we just found two different paths to reach this guy one that took one uh obstacle and another another that took two obstacles for us to actually get the minimum for a given position we'd have to visit it multiple times thus reducing the time complexity from like being efficient to being less efficient exponential probably and if we do not do that then there's no guarantee that when we do reach the last cell like maybe this is the first path that executes well it took three obstacles to get to the Target if we return that it's going to be the wrong answer so if we try to preserve the time complexity of BFS the optimal time complexity we will get the wrong answer so how do we reconcile these two things how do we get the correct answer and make it efficient well it's actually very very simple it goes back to making this a greedy algorithm consider this when we're here we could go to this side that takes zero obstacles and this side that takes one Obstacle of course we want to go through this part first and that's exactly what we did with the minimum Heap like the priority Q solution but how can we do it without a priority Q well the answer is basically you have a que you have a double-ended Q called a deck and here we have two neighbors one that takes zero one that takes one you take the zero and you add it to the left side you take the one and you add it to the other side the right side so I'll put it over here and uh just putting these in the middle cuz I think we're going to need this space and so now what I'm going to do is I'm always going to pop from the left side of the que that's usually pretty typical so I pop the zero first so it seems like it works out but how is it going to progress as we get to cells that take multiple obstacles how is it going to work well now once again I'm at a junction I can go down taking one obstacle I can go right taking zero obstacles I'm going to take the zero and add it to the left CU of course I favor this one over this one I'm still going to add this guy I'm going to add it to the right side one at this point we actually don't even need the image to help us just the fact that these values are always going to be in monotonically increasing order is enough for us to guarantee that this will always be the optimal solution let me show you what I mean just look at this deck for a second don't look at the picture right now my deck is 0 1 1 I'm going to pop the guy on the left maybe it's possible from here we can reach more cells that take zero in which case we add them on the left and maybe eventually we can get to the target with zero obstacles visited that would be great so this solution will work for that I think that much is pretty obvious but what if that's not the case what if now all of these take one obstacle one one well then in that case those neighbors are going to be added to the right side so I'll add them over here and now this is where it gets interesting for this guy I could either have obstacles that take just one now because it took one to reach this guy so in the best case the neighbors of this guy are also going to take one obstacle to reach in which case I would add those ones to the left side which is fine that there's nothing wrong with that the values are still in monotonically increasing order I will always process the ones that took the shortest path first but if maybe this guy's neighbors have two obstacles to get there the neighbors themselves have an obstacle thus it took two total obstacles to get there I'm going to add these twos to the right side like this and so now I'm going to process all of these maybe I'll end up adding some twos but I'm never going to end up adding like a three or I'm never going to end up adding a zero so all the cells that take two are going to be added in a section a block and then if there are additional cells that take three obstacles those are going to be added directly after the twos given a q like this we're never going to introduce any more zeros ever again that would be impossible so you can see that this solution is Trivial it's just BFS with a deck the only difference is we're not always pending to the right side of the deck sometimes we're pending to the left and sometimes we're pending to the right depending on whether there's an obstacle at the neighboring cell or not it's really that simple and it doesn't even require many code changes from the previous solution given that this is also a greedy algorithm so to optimize this I'm not going to rewrite the entire code because really all we need to do is change the Min Heap to be a q so I'm going to uh rename this to be q and I'm going to pass in to the deck Constructor this list it'll initialize it with just this tle and we are going to have the visit hash set still because once again we don't want to visit the same cell multiple times that will improve the efficiency of the solution I'm going to change this Loop to instead of saying Min Heap say Q I'm going to pop from the Q so I will keep most of this the same but just using a different function call Pop from the left side we'll get the number number of obstacles row column if we reach the target we can immediately return I have my four neighbors once again I'm going to go through the neighbors I'm going to have this if statement still be the exact same every time I add a neighbor to my que I'm going to mark it as visited the only thing we're changing now is this line over here let me delete it now there's going to be two cases now if the value at the neighboring row is a one that means it has an obstacle that means we're going to pend to the right side of the Q like this so I'm going to pend this Tuple obstacles plus one I could also say plus uh grid of neighbor row neighbor column because we already know that that's a one this would be similar to like what we did with the Heap but that's not necessary so just to keep it simple I'll just do a plus one and then we'll add the coordinates of that cell and so the else case is very very similar as you can imagine if you can imagine it I would pause the video and and try to guess what code I'm going to write I'm going to copy and paste this and make a small change just removing the plus one and not appending to the right side but appending to the left side with the function append left pretty simple right didn't require many lines of code and I think this is one of those things that would make a good interview question because let's say you were able to come up with the priority Q solution if I then told you how the deck solution worked I would expect you to be able to make minimal code changes to be able to implement that solution even if you weren't able to figure out the deck solution and really it's a BFS solution I think that's the better way to refer to it but anyways let's run this code you can see that this works and this one is more efficient if you found this helpful definitely check out n code. it supports me a lot and if you like my teaching style you will probably like the videos over there thanks for watching and I'll see you soon