Count Unguarded Cells in the Grid - Leetcode 2257 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem count unguarded cells in Grid this is kind of a fun one it's more fun to just think about the problem rather than coding it to be honest cuz coding it is pretty repetitive let me uh blow up this grid over here sorry about the colors I don't have much control over that okay I think that's a little bit easier on the eyes but the idea here is we're given a two-dimensional grid and we're actually not given the grid itself we're given the dimensions of the grid so for this example we are given M = 4 n = 6 M refers to the number of rows and N refers to the number of columns now if you were to swap these it wouldn't really matter it won't change the problem like if you just took this Matrix and rotated it 90° in either direction it would not change the problem so as long as you're consistent with how you use these two variables you should be fine the idea though is we're given two more parameters one is a list of coordinates called guards so that's what the G's represent so there's a guard at 0 0 at 1 1 and at 2 three there's also a list of walls and we're given three of them at 0 1 uh 2 two and it looks like one 4 so that's what this Matrix here represents and sorry I just realized that maybe the color scheme here was important for people who are color blind and maybe this is harder to see but if you can't see the colors that's okay because honestly what you want to be paying attention to is these arrows anyway all these cells that have like an arrow within them those are cells that are guarded so you can see this guard over here a guard can basically look in four directions I guess simultaneously don't know how that works but that's what they can do this guard can't look to the left there's nothing there can't really look up either can't look to the right because there's a wall there the wall is obstructing uh this person's field division but they can look down so they can see all these cells here this guard can see the same cell and it can see two additional cells and it can see a couple cells over here and this guard over here can see a couple here over here and then this additional one this one was already seeable by this guard so I guess it's double seen by these two guards um but I can see this one as well so now knowing all of that we want to then determine what are all the cells that cannot be seen how many of them are there it looks like 1 2 3 4 5 6 and then seven so we would return seven in this example so how exactly do we solve the problem well honestly even a pretty basic simulation will work but there's a way to make it slightly more efficient think about this for a second first of all remember that they didn't actually give us a grid if you try to solve the problem without a grid I mean maybe it is possible possible but it would be kind of annoying because think of this uh let's say we just iterate over all the guards the size of the Matrix is 4 * six so there's 24 total cells and then we say okay well we have 1 2 three guards so then a minus three from there we have 1 two three walls so minus 3 again and now we just have to count the cells that are guard and then we subtract that total amount so the problem just becomes figuring out how many cells are guard so you go through every guard and you say okay well this one can't really look in any of these directions but it can look down all three of these cells are unoccupied so we count them we'd subtract those three from our total as well and then you'd go to the second guard and do kind of the same thing okay you can see these two you can see these two and you can see this one but we already counted this one so how do we know if we already counted a cell I mean now you might get into the thought process of using like a hash set or something but why do that in the first place when we could just make the problem a little bit easier and just have a grid and then instead of counting the cells that can be visited we actually Mark the cells that can be visited and by visited I mean guard and so after we Mark those then the problem becomes pretty simple all we have to do is like after we've marked all of them we can just then iterate over the entire grid and then count how many cells can't be seen 1 2 3 and then you know it's going to be a total of seven that have a position that cannot be guarded and you might think well that's seems kind of inefficient doesn't it because for every single Guard we're doing in the worst case an operation where we'll have to scan entirely vertically and possibly entirely horizontally as well that's going to be an N plus M operation how many times are we going to do that well however many guards there are you could say that's G in the worst case G could be proportional to the size of the Matrix so it seems inefficient at first glance but think about the implementation think about uh this for a second like let me just kind of draw one row just to make it a little bit easier let's say we have a guard over here guard over here and we could have a bunch more guards but just to keep it simple I'll just kind of do something like this and let me actually get rid of this wall for a second let's say we go through this guard first we see okay it can guard this position and it can guard everything to the right of it boom boom boom and then eventually we reach this guard and at that point we don't really need to go any further because while we could keep scanning we already know we're probably going to visit this guard sometime in the future or maybe we have already visited this guard so we could stop right there similarly if this guy was a wall we could have stopped as well now maybe at some point in the future we're going to visit this guard as well we're going to go in both directions we're going to go to the right and then we're going to go to the left so we'll maybe end up revisiting these cells is it really that big of a deal because it's not like it's going to be visited more than than twice like this entire row isn't going to be visited more than twice none of these cells should be I mean maybe if there's another guard up above and they'll scan like vertically we might but still in the worst case I don't think a cell will be visited ever more than four times in the worst case there might be a guard above and there might be a guard below it but basically what I'm getting at is even though this solution might not seem that efficient in the worst case I do think it's proportional to the size of the Matrix somebody can correct me if I'm wrong but I'm pretty sure the way I'm going to be coding it up at least as long as you kind of initialize all the guards within the grid before you start running the simulation it really shouldn't be much more inefficient than the size of the Matrix and practically speaking it's not like we're going to have a ton of guards most of the time so this solution should be pretty efficient let's code this up so the big thing is just kind of having a matrix I'm going to initialize it to be all zeros so there's this many columns and then we're going to have this many rows M rows if you don't know what this syntax is about this is list comprehension I cover it pretty in depth in my python for coding interviews course has a bunch of interactive lessons if you're interested in that but we're going to be representing four different states within this grid let's say zero is free let's say one is a guard let's say two is a wall and let's say three is a Gable position we kind of need to distinguish between this and all of the others so it does make sense to give this its own uh State and then we add the guards and the walls to our Matrix so let's say a row column in guards because guards is a list of pairs we're unpacking the coordinates of each guard and then we're going to mark that guard with a one we'll do the same thing with the walls just like this and we'll mark that with A2 so now what we're going to do is iterate once again actually over all the list of guards like this for row column in guards and then we're going to run a helper function I'm going to call it Mark guarded so for this particular position we know there's a guard here so we're going to go in all four directions I'll Define that helper function up here call it Mark guarded passing in row column pair you might think well looks like I'm kind of having two similar Loops here why don't I just throw this in there or maybe move this above the loop over here and then I can combine these two Loops no that's going to make the solution inefficient for reasons I kind of talked about earlier that is going to sort of break the guarantee where a cell will only be visited at most four times if we don't do it that way we could end up in a situation where we keep visiting the same cell several times and the reason for that is because in this function we're now going to go in all four directions so uh let's say from left to right so I'm going to say for Row in range r + one because we know this is the the coordinate we're at we want to go left to right I guess this is really going top to bottom cuz we're incrementing the row but we're going to go from row plus one to the last row so we'll say m m is the number of rows and we want to basically Mark all these cells as Gable so we want to say row column and so this is was the coordinate of the Guard so here we actually want to use this variable that we're uh calling row I know the variable names are a little bit confusing so just kind of have to be careful about that this is the guard row and this is the direction that we're going in so we'll mark this with a three now remember there is a case where what if we had a wall well at that point we'd stop iterating so if we say grid of row column is equal to three we want to stop iterating or sorry not three a two walls are two but same thing if we see a guard at that point we don't have to continue looking we know that that guard will be able to see in that same direction anyway so at that point we'd be able to stop so I'm going to put a break statement inside of this condition and I'm going to change this equality to an in operator if this is in either one or two if it's equal to either of these then we want to break and so I want to do the same thing that I'm doing here except going in the opposite direction so what I'm going to say is here starting from row or rather I want to go from zero to the row but I want to go in reverse order so I'm going to do this reversed and remember that in Python the row here is non inclusive so we won't actually be visiting the starting coordinate we'll go everything to the left of that from right to left this looks correct to me and if you're unfamiliar with some of these like tips and tricks I'm doing I believe I Do cover them in my python courses on N Cod iio so now we want to do the same thing except Shifting the column so I'll say for column in range from column + one up until n and I'm going to have some similar code as this so I'll go ahead and just copy and paste it in there except this time the row is going to stay fixed and the column is the thing that's going to be shifted same thing down here and so we also want to do the same thing in Reverse so let me go ahead and just copy and paste that so going from zero up until the column but not including the column but we want to do this in reverse order so just wrap that in a reversed and I believe this is good I might be missing something it's really easy to make a mistake when you're copy and pasting code but I think this is mostly correct and you can see why this code is pretty repetitive there's nothing really interesting about it I think that's more or less the entire code well almost all of it so now that we've kind of updated the grid we've set the state of the grid we just have to count the number of unguarded positions so I'll set that in result that's where the count will be I'll go over every position in the grid I don't actually have to do the positions I just need the value of each position so I can do this in Python for every Row in the grid and then for every row I want to get the value so for every n in the row if n is equal to zero it's not guarded so I can increment my result by one and then after that that's what I want to return this result value so that's the entire code I'll zoom out it's going to be hard to fit all this in one screen so I'll have to kind of get rid of these empty lines sorry about that but this is the whole code let's give it a run and you can see here that it works and it is pretty effici for reasons I talked about earlier there is a slightly different way to implement the solution which will have the same time complexity it's actually guaranteed to be the time complexity like M * n so I'll briefly talk about that solution and then I'll just show you the code of it it's also pretty repetitive I think it's even longer than this so let's quickly talk about that so this is one of the ideas that I came up with it's kind of similar to what I had talked about earlier suppose we had a row and we could have had several guards we could have had a guard there a guard here a guard here and we could have had some walls in between or not we want to Mark let's say horizontally the cells that they can see in horizontal Direction so we can go from left to right so we're going left to right we have some empty cells here we don't do anything with them we see a guard now okay now that You' seen a guard every time you see an empty cell now Mark it as Gable so I'll just mark it with a red and then a red here and now we see another guard here so we're not going to mark this as red but we'll continue marking these had we not seen a guard maybe instead here there was a wall at that point we'd say okay now these cells are not going to be guard so we would leave them as free had this been a wall so then we' keep going to the left now we see a guard again so now we're going to say okay everything we see after that should be guard now you might have noticed something this only covered the guards seeing in the right direction maybe there is a way to do this with one pass and having the guards see in both directions but I think implementing it is a lot easier if now you just go through this entire row in the opposite direction so now I'm going to go from right to left and these are already guarded so now I see a guard here now these are going to be guarded I see a wall here so I'm not going to Mark these as guarded but they're already marked as guarded and then I'm eventually going to see this guard so I'll mark everything to the left of it as guarded so you can see how this works on a single row and there's no reason we can't apply the exact same when we're doing it with columns because geometry I mean you rotate this thing 90° how does that change the problem it literally doesn't change it at all just kind of a basic fact of geometry but as you can see this code is going to be pretty repetitive it's going to require us to over uh the input grid here go through every row like this and then go through every Row in the opposite direction so you do that like visit each row twice and then you do the exact same for every column this basically guarantees that we're going to visit every single cell four times whereas in the previous solution the upper bound was that will'll visit every cell four times so this solution actually even though it's guaranteed to be M * n you'll see that this solution the real runtime is actually less than the previous solution even though like the code of this solution isn't super interesting I do think this kind of complexity analysis is the most valuable thing from this problem I hope you understand why this solution is less efficient than the other one and if you don't maybe you want to rewatch that beginning of the video where I was talking about the complexity analysis so I'll briefly walk you through this code most of it's pretty similar the setup is the exact same we have a matrix I guess you can see the comments that I had when I was coding this one up for the first time as it says just go through rows and columns in both directions so I kind of just did it without simplifying the code at all so you can see here I go through every row I go through the row from left to right right I go through the row from right to left I have a Boolean flag which tells me have we seen a guard before and if it's true uh here we'll be marking empty cells with a three because then they are guard if I see a guard I will set the flag to true if I ever see a wall which is two I will then set the guard flag to false and this is doing it with the rows the bottom code here doing it with the columns is pretty much identical just kind of flipping the direction that we are going in and then after we do that we do the rest of the code the exact same just count up how many cells are not guarded so I'll show you that this code does indeed work and I'm sure it will not be as efficient so running it you can see yep it is less efficient but I think it's not that much less efficient let's compare the exact runtime so this one was 471 milliseconds whereas the previous one was 293 so you can see it's not like it's an order of magnitude faster it's like maybe twice as fast or a little bit less than that but both of these Solutions are proportional in efficiency if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon