Map of Highest Peak - Leetcode 1765 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today we're solving map of highest peak so this is a very classic and good problem in my opinion I would say the solution to this problem is almost identical to two problems in the neat code 150 list uh this list over here that I think most of you guys probably already know about but in the graph section there is two problems walls and Gates and rotting oranges that has a very very similar solution to today's problem and if you want to like look at those problems you can uh see them here uh but let's get into this problem now the idea is I'll kind of give my own explanation rather than like reading through all of this we are given a binary Matrix I know that doesn't look like a binary Matrix over here but imagine that what we were originally given looked something like this first row is 0 1 next row is 0 0 so specifically what this means is that zeros are land cells and ones are water cells it's a little bit backwards at least from what I would expect and then we're given a couple rules so I think one of the hard things about this problem is probably just trying to interpret it what they are telling us is that we must assign a height to every one of these positions what we're given is not the height itself zero is not really a height one is not a height all this means is that we have to assign each of these positions a height the good thing for us is we actually don't need to assign a height to the water cells that is actually given to us the height of those must be zero so when we create the output Matrix for that corresponding position obviously we're going to have a zero in that spot so that's like the easy part the rest of the heights must be non- negative 0 is technically non- negative so that's fine and this is probably the most significant part any two adjacent cells must have an absolute height difference of at most one so when you look here this is the output Matrix like this is the result that we would return you can see that down here and you can see that it indeed is the case these two adjacent positions have a difference of atmost one these two have a difference of atmost one these two are not technically adjacent when we say adjacent we only mean the four directions and this guy indeed has an absolute difference of atmost one here and atmost one here so why is this the result I mean technically it does meet all the conditions but why did we pick this Matrix couldn't we have also made this guy a one or we could have also made everything in here a zero that is technically non- negative and the absolute differences are zero well the reason we didn't do that is because what we're trying to do is find the Matrix such that the maximum height in the Matrix is maximized so right now the maximum height is two and indeed it is maximal there's no way to actually create a matrix that follows these conditions that has a value greater than two it's not possible and I think it's kind of obvious in this small example why that's not possible because think about this for a second in this Matrix over here we knew that zero has to go in the top right position and then from that zero if we're asking okay for my neighbors I only have two neighbors what is the max possible value that could go here well it's probably one cuz that's one bigger than the previous value since we're trying to find the overall maximum value we're trying to get the maximum height somewhere in The Matrix we should try to be greedy if our value currently is X whatever you want to call it X is equal to zero right now then our neighbor should always x + 1 because x + 1 is the maximum value we could put here because we need to make sure that the difference stays uh one so for both of the neighbors from that guy we will obviously put a one we're trying to be greedy and ultimately we'll end up with a two over here and then this is the Matrix that we would return now what I kind of just did right now was from the water we pretty much performed a traversal specifically in this case it was kind of a breath for search traversal where we went layer by layer and we said okay this uh first layer from the water source is going to be one the next layer is going to be two and if we had a larger Matrix then we would kind of keep expanding each layer it's easy enough when you only have a single water cell but what happens when you have multiple water cells suppose we are given a 3X3 Matrix so the original Matrix looked something like this we had a one over here and a one over here and then the rest to these were zeros and so what that really means is that we would create our own output Matrix initializing everything to be empty except for these two which would end up being zero and then what we would want to do is from each of these water cells at the same time we want to run a BFS from both of these at the same time what it is specifically called is a multi-source BFS the good thing is that implementing it is pretty similar to just implementing BFS so if you're familiar with that you should be good to go if not you should consider checking out n code. to really understand this fundamental algorithm that comes up a lot the idea behind BFS is that we usually have some kind of a q data structure so I will draw that down here it's kind of hard to draw it mainly because we're going to be using like the coordinates of this grid which are going to be something like this and then initially what we want to do is add both of these to the que at the same time so we would have something like one Z in the Q and then 0 two in the que I won't like draw too much of this part but just know that what we're going to be doing is popping so we pop this which is going to be this guy and then we are going to look in all four directions at its neighbors and give them a height one greater than this one so for all three of the neighbors we give them a height of one we know that that's the maximum they could possibly have because they are right next to a zero right now then we pop one more time we pop the 0o to this guy we look in all four directions there's only two valid directions we don't want to go out of bounds so that's something we'll have to keep in mind when we code this up but uh for this part we just look at the two neighbors and we give them a one and a one over here when we added these like five neighbors we would have also added the coordinates of these five neighbors into the Q so let's just arbitr start with one of these three let's say I ended up doing this one well I would look in all four directions it's mainly just this direction and we would give it a two and then I would probably end up popping the rest of these so right now I pop this this this and let's say I go through here next I'm going to look in all four directions everything's already been filled like this guy's already been filled down here is already filled so we don't need to do anything we don't want to revisit the same position twice we don't want to say let's give this guy a height of two because this one had a height height of one that's not possible because this is right next to a zero so once we fill in a Cell we know that we're done we know we've already given it the max possible value if we see it again do not assign it a new value um after that we will end up popping this popping this and then eventually I think we'll get here or here well I think this will be first so we'll pop from here we'll look down we can give it a 1 + 1 which is two so we're done with this eventually we would pop here and realize we have nowhere to go we'll pop here again nowhere to go we filled in every single cell we pushed it and popped it from the queue in order and we are done you can see that if I well you can't really see all the values here but it is identical to the Matrix on the left you can see we have a couple zeros in these spots and then these two are twos everything else is a one so this is the idea behind this problem it's a bread for search that has multiple starting positions similar to the hard problem that we solved ear but this problem I think is just much more reasonable much more easy but conceptually it's the same so let's code this up in my original code I had three values pushed to the que I don't know if that's actually more simple for people or not I think you don't actually need to have three values in the queue you can actually not have the height so when I cat it up now I'm going to try to do it without the height and yeah this is just a BFS from the water so I'm going to start with a little bit of boiler plate first here I'm just getting the dimensions of the is is water Grid it's a binary Matrix to start with zeros and ones I'm going to have a Q and I'm going to have a visit hash set so what I'm going to do here first phase one is get all water cells and add them to the que so I guess I could say andq all water cells so we're going to go through the entire Matrix that's pretty straightforward with some nested Loops we can check for each cell is water at this position if it's one that means it's water otherwise it's not so I could uh check if it's equal to one or just leave it as is and I want to do a few things here one I want to add these coordinates to the Q This is a water cell so we want to start our BFS from this cell I also when I enq a node I want to mark it as visited because I don't want to ever add the same node to the que multiple times so I can say visit. add row column you could probably get around not using a visit hash set and just use the Matrix that we're going to end up returning in the output but I'll continue to use a visit hash set just to keep things simple so I'm going to have my result it's going to be a matrix which is going to be all zeros initially I could also make it all negative 1es and I guess I'll actually do that just to be a bit more readable and so this will have this many values in a given row and it'll have this many uh columns or rather this many rows sorry so this is just a matrix of the same dimensions as the ISAT Matrix with a bunch of negative ones filled in so now in this Loop we can say that since this is a water cell at this position in the output it will have a value of zero not1 and so after this we can start our BFS it might be a multisource BFS depending on how many water cells we had or maybe it'll just be a regular BFS that's what I mean by this part of the code is pretty cookie cutter it's pretty simple it's always just BFS this is the part where we have multiple sources in our BFS so down here all I can say is while q q. pop left we get the row column coordinates and to get the height of these coordinates well that's the good part we can just look at our result and then say this height is equal to that next we want to go through the four neighbors of this current position so first I'm just going to create an array of neighbors so we don't have to have like repeated code we can just Loop through the four neighbors and each of them is going to be one position adjacent so row + one column + one uh row minus one and column Min - one next we will go through those neighbors so like this and we can unpack each neighbor row and neighbor column as we kind of go through it it's a array of pairs and so what we ultimately want to do is this we want to append to the que this neighbor neighbor row neighbor column we also want to mark it as visited so we can say visit now that it's been added to the queue we can add it to the visit hash set as well and lastly we can give it a height that's kind of the most important part we know that the neighbor that we just came from had a height of this and we know that this is the first time we're visiting this neighbor so we can give it a height in the result of plus one so H+ one and that's for the neighbor not the original so let's do this now the only problem here is that we don't know that this position hasn't been visited yet and we don't even know if it's in bounds so let's check that first let's check if the row was out of bounds or the column was out of bounds in either direction so n row is equal to rows or n column is this in that case we would continue to the next iteration of the loop and we would skip this code down here there's one other thing that we need to check for and I'll add that condition down here which is that this position has already been visited so if this pair is in the visit hash set then once again we can skip that iteration and after all of that is done down here we can return the result so provided I don't have any bugs this code should work and yes you can see here it works it is pretty efficient I can promise you that at least in terms of Big O runtime I'm guessing that the hashset is is part of the reason that maybe we could slightly improve the runtime so actually let me try that very quickly so let's get rid of the visit hash set and see if we can work without it so here I added it to visit I can get rid of that and let's say negative 1es are unvisited spots so1 is equal to unvisited and we can use those semantics to fix the rest of this code so rather than checking if this position is inv visit we can check if uh the result at new row new new column is not equal to -1 because if that's the case that means it's already been visited and so down here we also don't have to mark it as visited and we also don't have to do anything I think this is marking it as visited implicitly so hopefully I didn't miss anything and I can just run this code AS is kind of hard to see all of it at the same time so hopefully if I just zoom out a bit I guess but this is the final code and yes you can see it actually does work and it looks like it did actually make a measurable difference it looks like it was twice as fast as the previous solution but in terms of Big O runtime I can promise you that the solution didn't change but uh practically speaking it did make it more efficient if you found this helpful definitely check out n code. thanks for watching and I'll see you soon