Regions Cut By Slashes - Leetcode 959 - Python

Key Takeaways

everyone welcome back and let's write some more neat code today so today let's solve a problem regions cut by slashes another fantastic problem to solve it's actually a pretty interesting one the idea is we're actually given an array of strings where it's going to form an N by and grid I don't know why they couldn't have given us like an array of characters a grid of characters but oh well this one for example would look like this I'll draw it out cuz it's easier to visualize than these uh strings so imagine we have this 2x2 grid there could be empty spaces or there could be back slashes or forward slashes I think that's a forward slash I might have them mixed up but anyways so this one in particular you can see has a forward slash here and here so now if you were to count the number of regions that we have like this is a boundary and this is a boundary clearly we have one region over here and a second region over there so immediately if you don't even look at the other examples in your mind you might think to count these regions sounds similar to like number of islands or one of those core problems in the N code 150 list if you've gone through that list while it would work in this example this first one we would run a DFS from every empty position marking them as visited so we'd mark this one as visited and we can't really visit this one cuz it's divided so we kind of just ignore those maybe we consider them as like blocked positions and then we'd count another one over here so that's two so the goal of this problem is to count the number of regions that we have and in this first example it works we get two but it's not going to always work it would probably work in this case I guess so you know this is blocked out and then we'd get this region counted with a DFS you could also use BFS these are just core graph algorithms that I cover very deeply I think on N code. bunch of animations and all that actually I think this would be a good time to kind of show those animations just in case you don't know how those algorithms work so I'll play this one at 2 XP just to kind of go through it this is kind of a similar grid where let's say the ones are marked off and zeros are not marked so DFS is just going to kind of go as far deep as we can in any particular direction and this one is looking for a path we're not obviously doing that in this problem but the core idea is the same you can check these out on like nikio on The Matrix DFS and BFS I have another one for that here as well going to the third example it's not going to work cuz look at the grid that we have we have something that looks like this where we have a slash there a slash there here and here now technically counting these this is one this is two this is three this is four and then in the middle we have the fifth one but our DFS isn't going to work because we considered these ones as like blocked off so how do we do it well the first thing you might think is well just because we have a slash here doesn't mean that this is blocked off maybe we can split this up into multiple cells like say okay this is one this this is the region that's blocked off and then this is two these are open it's kind of complicated to do that like doing just two cells wouldn't work cuz you have obviously two empty regions and then one like line doing three regions is strange because we can't get enough information from that you could say that these are open and then the middle is blocked here but the one below it would kind of be the same thing and obviously these two are not equal right this is a slash going in a different direction the other thing you might think is well this is a square so if we want to make it bigger we should create another Square maybe a 2X two square for every single one of these and honestly it's not a bad idea at least that's what I think because that's what I was able to come up with and unfortunately it didn't work let me show you why it doesn't work so scaling this example will have a 2x2 square for each of these so let's say we have four 2x two squares let's draw the line here let's draw the other one going there this one and this one in this example it actually does work that's why it's misleading you run a DFS over here okay you get this one and then you run a DFS from here you'll get this this one this one and this one and then you run the DFS there there and there and so I think you would correctly count five here so this is a DFS going in for directions but it's going to fail for some examples let me show you suppose after scaling we end up with something that looks like this so This Square had one slash this one had a slash this one had a slash and this one had a slash so you can just imagine that the input would have been literally this like two slashes in the first string and then two slashes in the second string and then after scaling this is what it would look like so you might see the problem here run a DFS over here that's one region I mean in total we clearly have 1 2 3 four regions so run the DFS here you get it great run the DFS uh maybe from here okay well the DF is only going to mark this remember our DFS goes in four directions left down right up so it's only going to get that that'll count one then run the DFS over here eventually cuz we're only running DFS from the squares that don't have a slash run the DFS here then here that's three that's four that's five that's six that's seven so clearly we miscounted them okay now your approach might be the brilliant idea that I had why not let ourselves go diagonally isn't that such a smart idea well unfortunately it's not can you look at the picture and tell me what would happen if you can you're smarter than me yes going from here allowing ourselves to go diagonally here would count these as well but do you see it would also count the ones going top right well that's not a problem going top left well that's not a problem well going bottom right that might be a problem we're not allowed to go through the line and how would we possibly know that we went through a line doing it this way isn't going to work so basically long story short we can't just scale this up to 2x two we need more space here so instead let's scale it to 3x3 so each character in the input is going to be its own 3x3 grid so let's see how that would work with this example remember this is what the input would be so we'll get a 3X3 Square for each of them this might not be the cleanest so now we can put the diagonal here the diagonal here here and here as well so now let's try it okay run the DFS from here we'll count that that and that that's one region so then we'd probably run the DFS from here and then get that that that that and that and all of these as well actually so that's the second region and then eventually like we wouldn't redo any of these cuz they're already visited and eventually we'd get here and then get the third region I'll kind of go fast now cuz you get the idea and then eventually we'd go down here this is the fourth Reg so 3x3 is enough we won't run into any sort of issues at this point the problem just becomes take the input scale it to 3x3 grids for every single character if we have an empty character then it's just going to be an empty 3x3 grid if we have a forward slash then it's going to look like this if we have a back slash then it's going to look opposite so it would look something like this going in the other direction and then once you have that grid that's three times the size as the input you just run DFS it's pretty much just number of islands at that point just count the connected regions that you know don't go through any of the lines so the last thing you might wonder is well how exactly do you scale it well we know obviously the size of the grid is going to be three times the size of the input that's not hard to initialize but when we get to a one by one grid for example so for a second just kind of assume that this stuff isn't here well I guess I can just kind of clean it up imagine this was our input and this would have been in the form of a string so like here given these input strings we'd have a 1 by one grid that looks like this imagine we wanted to put that over here well we'd see that okay the first character is empty so the first 3x3 grid should be empty the next character is a forward slash so we need to put a slash there so what do we do well we're going to start at the row and we're going to get all three of these rows and we're going to start at the top right put like an X there or just block it out and then block this one out and then block this one out as well it doesn't really matter how you block them out actually so if we were going like this or we had a slash that went in the other direction it doesn't really matter as long as you have a way to indicate the free spaces versus the blocked out spaces you can use zero and one so that's what I'm going to be sticking with let's say zero is empty and ones are blocked there's that but now let's actually look at the indices for this so this was 0 1 2 3 4 5 this is 0 1 2 and continuing over here we have 0 1 and then 0 1 now the pattern is going to be when when we see one over here this is going to correspond to this quadrant like this 3x3 Square how do we know that though well we just take the row and multiply by three that's going to tell us the starting position if you took this and multiplied it by three you'd get zero and then you'd say the next three belong to this guy same thing over here you take this multiply by three then these next three belong to this guy if you took the next one which would be two multiply it by three you'd start at six that is clearly a pattern that works and it would obviously apply the same way from The Columns as well cuz the math is going to be the exact same it's still 3x3 so that's pretty much it that will tell us the starting row and the starting column this will kind of be the top left if we were doing a slash like this we'd take that and add one to it to both the column and the row to get this one and then add one to it again to get this in the opposite case we'd be here but we would want to start there so we'd probably add two to the row and then just go in the other direction I think that'll just make more sense in the code the overall time complexity is just going to be 3 times the dimensions of the input grid since it's a square Grid it's going to be n^ S so 3 times that is still going to be Big O of n^ 2 we're obviously declaring extra memory for this so the space complexity is going to be the same let's code this up so I started with a little bit of boiler plate we just get the dimensions of the input grid I call that rows one and columns one we multiply each of those by three to get the dimensions of the second grid which we're going to declare down here so it's going to be each row is going to have this many columns and we're going to have this many rows so this is just a two-dimensional grid of all zeros initially so next we can have a couple nested Loops to go over the input grid and then map it to the second grid so something like this now there's only two cases cuz remember the third case is where the grid is empty at that position and we don't really care about that so we can check that either this is a backslash I think that's a forward slash honestly I'm not sure or that it's a slash that goes in the other direction like this and the reason we have two characters here is because by itself this is like the Escape character so like for example like see we have like double quotes around this what if I wanted to type something like hello like I wanted to use the quote characters inside of that string well that's what the slash is for like this would print the string hello with quotes around it so the Escape character is used for that so we need double of these to say that we actually want the character itself anyways now we do the scaling before we even start that let's get the top left of the current 3x3 portion that we're trying to get which we can just take row and multiply it by three same thing with column and I'll assign these to a couple variables I'm not creative so I'm just going to do row two and column two this tells us the top left so let's start with this one because it's actually going to be simpler top left is R2 and column 2 and we just want to put a slash through it so this is going to be one and then we're going to copy this add one to both of these to get the middle spot and set that to one as well and then copy this and then add two to each of these to get the bottom right spot in that 3x3 Square so now let's do the other side I'm just going to copy this so we don't have to type it all out so this we want to be the top right so row stays the same but column is going to be plus two this we want to be the middle it already is so that's fine this we want to be the bottom left row plus two is good column though should stay the same so there we go we're going to use a DFS and I'm not going to implement it just quite yet I'm going to show you how to use it first we're going to count the number of regions and then we're going to return that so let's do that by going over every position in the second grid so do rows two here make sure you have that correct and for every column in the second grid columns 2 and then we want to run DFS on it so row column and we don't want to visit the same position twice so let's have a hash set which I'm going to call visit I'll zoom out a bit I call it visit and that's what we're going to pass in here now there's no need for us to run DFS here if this position is already visited or if it's a like slash character or rather in our case a one cuz that is blocked off so let's have an F statement here if the Grid at this position well grid two make sure you have that correct if Grid 2 at this position is equal to zero and this coordinate has not been visited it's not in visit then run DFS so we found a new region that hasn't been visited so we can also increment the result by one here so this is all of the code the DFS is actually going to be shorter than you think the main thing is definitely the base case so if we ever go out of bounds if row is less than zero or column is less than zero or we reach the edge row is equal to number of rows or column is equal to the number of columns or of course we reach a position that's not zero that means it's blocked off so Grid 2 make sure you have grid two there is not equal to zero or it's equal to one or this position is visited row column is in visit then we would immediately return we don't need to keep going that's also remember to add the parameters here to the DFS so row column and visit so if this is not the case then we want to do our DFS so at this point we can mark this coordinate as visited and we can go through the neighbors of the current row how do we get the neighbors well the easiest way to do it is just to create an array so we know that we only care about the Neighbors in the four adjacent directions so we can take row column copy and paste it a few times like this and then add one to each of these so add one to row add one to column uh subtract one from row and then subtract one from column so that gives you the four directions now we want to go through those four neighbors we can do that like this for neighbor row neighbor column in Neighbors so this is using unpacking we're getting both of the coordinates at the same time because because we have an array of pairs I cover this in my python for coding interviews course if you are interested in learning about that but we have the coordinates so now we can just do the DFS on the neighbor row neighbor column passing in the visit hashset so I believe that is correct I really hope we don't have a bug because coding all this up even though it's only I guess 36 lines of code it was still kind of a pain so let's make sure that it's correct and of course I mentioned it multiple times but I still made the mistake uh I used grid one here we're trying to map grid one to grid two so I got to replace these with grid two so I'm going to quickly do that to all of these I'm really sorry about that whoops but now I believe it should work and once again I had a typo in the name so this should be row two and this should be columns to I guess that's a reason to have more descriptive names so I apologize for that okay now it works and while the runtime doesn't seem efficient this is pretty much as efficient of a solution that you can get I mean if you can think of some more optimizations feel free to let me know but if you found this helpful check out N.O for a lot more thanks for watching and I'll see you soon