so we have learnt about the bfs traversal and the dfs traversal but where will it be applied so you're going to do a bunch of problems and this video is going to be about the first problem number of connected components so let me explain you the problem so what does the problem state the problem states uh you'll be given a grid of size n cross m where n is the number of rows and m is the number of columns in the grid and uh are meaning i uh water and one is meaning the land okay so your task is to find the number of islands and an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or direct uh diagonally in all eight directions so basically what they are stating is they'll be giving you a grade of size n cross m okay oh yeah zero means water one means land now you have to find the islands so this is a land this is a land this is a land this is a land this is a land so i can say these all lands are connected these all lands are connected because this can be connected like this this like this guy is connected to this this guy is connected to this this guy's connected to this this guy's connected to this or you can take the other way these guys are connected these guys are connected these guys are connected these guys are connected they are connected in somehow because all the eight direction connectivities are allowed all the direction connectivities are allowed so i can say these piece of plants are connected and then there is water water water water water and then these piece of land is connected and this piece of land is correct so apparently i find three pieces of land or three pieces of island first island second island third island so there are three islands so the question states tell me the number of islands tell me the number of islands if i give you a grid now you might be thinking about striper this is a 2d matrix how can this be a graph problem this is a craft problem so try to think it as a note try to think this as a node a node a node a node a node a node a node a node so all these guys as a node okay so if you think that all of these guys as a node or a vertex carefully observe this guy is connected to this guy this guy is connected to this this guy is connected to this this guy's connected to this so can i see if i start the traversal it can be any traffic bfs dfs doesn't matter if i start a traversal from one this will make sure it traverses the nearest one this will make sure travis is the nearest one this will make sure travis is the nearest one this will make sure travis is the nearest one so if i start from a particular one and i do a certain level of traversal assuming assuming that the connections are in all the eight directions then this one will go and traverse this this one might go and traverse this this one might go and traverse this this one might go and traverse this they cannot go beyond this because there is zero zero zero zero zero zero zero zero zero all over they cannot go beyond this so if you do a traversal starting from this one this will go and touch all of these guys and that can be called as one entire bfs or dfs whatever you do so i can do one traversal and that will touch this right and then can i see from here if i start the next traversal this will touch these two things and the third travis if i do from here it will touch so can i say in short if i do three traverses if i do three traversals three starting notes one can like out of these i can pick up any one as the starting node any one is the starting node and it will make sure it visits everyone again among these two i can pick up any one as the starting node and it will make sure it will touch these two and from here i can pick up any one and this will make sure it only touches it so can i see if i take three starting nodes yes if i take three starting nodes i will be able to touch all the pieces of plant thereby can i say there are three islands because one starting node will make sure it touches all the connected lands so one starting node will represent one island so this is the intuition so we have understood kind of the intuition but how do we apply and traversal technique that we have learned in the previous videos so we know couple of traversal techniques one is the bfs while the other one is the dfs so probably we can just uh try the bfs transfer technique and then we can think of something uh okay so what does bfs take bfs states give me a starting point so i'll say okay this is the initial starting point and you can just refer this by instead of node numbers you can refer this by this row zero and column 1 so it can be the starting node can be represented as row 0 column 1 so instead of a vertex number we can represent it by a row and a column number now a pair of row and column so i can say this is the starting node now what did we do initially in the bfs if you remember initially what we did was we took a queue right we took a queue and we inserted the vertex and what is the other thing that we did we always went ahead and marked them as visited in the visited array but over here the vertex numbers are in pairs so we need something as a 2d array to mark visited so what we will do is we will create a replica 2d array yes a same size 2d array can be easily created yes a same size 2d array can be easily created so please go ahead and create the same size 2d array once you have done this this is 0 and 1 pushed into the queue initial config 0 and 1 will be marked as visited or 1. so this is the visited array please mark them as visited done what is the next thing that you will do they'll be like fine what does bfs said mean bfs send me while traversal pick up the element from the queue i'll pick up the element from the cube perfect and then it said travel to all its neighbors and in the graph we stored all the neighbors in something which was known as adjacency list remember but over here what we will do is we don't have an adjacency list but we know who are the neighbors if i'm standing at a node the neighbors can be someone at the top someone on this diagonal someone on this diagram someone in this one someone here someone here someone here someone here there are eight directions who can be neighbors we know the eight directions we know that there can be eight directions so what we will do is we will go to all directions so does it have a neighbor on the up so that does not exist does it have it here no does it have it here yes we have someone and that's on the row zero and column two row zero and column two so go and mark it perfect next does it have it here yes that's on row one and column two row one and column two mark it next does it have it here yes that's on row one column one mark it next does it have it here no it's a water does it have it here no it's a water does it have it here invalid over so i decided all the eight boundaries and i got three guys who were lance take it and we are done for the first traves for the first travis we are done let's pick up the next guy which is zero two now who is zero two this guy is zero checks for all its neighbors in the same way this guy's already visited does not take already visited does not take already visited does not take does not gets anyone perfect one two so we get one two now which is this guy so we have one two so for one two this is visit this is visited water water water we get a new guy who's at two comma two so two comma two is marked as visited perfect then water marked as visited marked as listed marked as listed so this guy only got this neighbor in all eight directions which we have taken perfect next we get one one and one one is this guy again visited visited visited water water water water done one one is also done next we get two two add two to what happens which is to do this is this visited water water water water water water visited visited visited so we get no more neighbors thereby tutor is also done apparently the queue becomes empty apparently the queue becomes empty so this is how if you do a traversal you will touch this this this this this this so you saw how in one traversal you could have done dfs as well how in one traversal we were able to touch everyone the lands that were connected to it done next we we have to start from this guy which is the starting point will change and this time the starting point will become four comma zero and again we'll follow the same process and if we follow the same process again it will be marked right so the next time the starting point will be this which is four comma three again the same process and this guy will be marked so apparently there were three starting points that we used there were three starting points that we used so how will you decide the starting points very simple what we will do is we know it's a matrix we know it's a matrix so we start from this guy which is zero comma zero and we say it's a water no need to do next we go to here we find it's a land we start the bfs traversal from a land we start the bfs transfer from a land and this is my first starting point this is my first starting point and this will make sure it visits everyone next we got this is done this is done next we go to this and this says i'm already visited man i'm already visited someone visited me no need to do a bfs i cannot be a starting point because i was already next we go here water water he says hey i'm already visited next we go here already visited water water water again this guy says i've already been touched water water water water water next you come over here and you say i have not been touched i'm not being visited you need to consider me as a starting point and this will touch both these guys next you go here he says i'm touched whatever next you go here i'm not touched i'm not visited you have to do a starting point as me okay so you got three times as a starting point you got three times as a starting point so if i kind of tell you the pseudo code now you know the bfs traversal is kind of simple so if i tell you the pseudo code it's going to be somewhere like for the row number like if i say no row is going to be from 0 to n and then there will be column number which will be from 0 to m and what you say is if not visited row and column what you do is you call the bfs with those row and column and at the same time you say these are the number of starting points that i called for so apparently this portion will count every time you call us row column to be the starting point you count it and bfs will stay kind of similar only you just make sure how to traverse in the adjacency list so we kind of wrote the pseudo code so i'll now get back to the editor and i will tell you how to write the code like step by step again the java code is on the left and we're writing the c plus plus code on the right so just in case you have an issue uh you are following java you can definitely check out the left part okay so what are we given we are given the character grid zero or one it will recommend water so what's the first thing i told you we need to create uh like we need to get the n so n will be very simple you can just say great dot size that will give you the n and you need to get the m as well so you can say create of zero dot size right that's something which you can say what is the next thing that you will do you need to create a visited array so since we need to pass everything by reference it's better we create something like this okay now we need to create visited so vector of int and m comma zero so everything is marked as zero now what is the next thing that you'll do you will be like okay the rows will be from zero and rows will go till n and there will be row plus plus and then there will be columns so columns will be from zero columns will go till n and column plus plus perfect and now what you'll say is if not visited row column right then you can just keep a counter plus plus and you can call the bfs for this row column with this visited and with this grid at the end of the day you can just go ahead and return the number of components which is the number of islands and over here you can just initialize count equal to zero now your turn your time now to write the bfs code so let's quickly try out the bfs so what i'll do is you can write the dfs as well that is completely your choice i'll leave it to you so i'm writing the bfs you can write dfs as well i'll show that to you as well so ind row okay anti-column that's the starting point as the next thing that you'll do you'll take the visited guy so visited guy will be taken always make sure you pass with reference and then you can definitely take the grid as well which is this and once you've done this you come back to here that was the first thing that you do always you say visited of yes that's the initialization equal to one that's the next thing that you do you took a q but this time since you're carrying couple of guys please make sure you carry something like this you secure.push off row comma call done what's the next thing that you do you i trade on the queue simple bfs simple bfs guys you write it on the queue right and you get the row as q dot front dot first and you get the column as q dot front dot second once you have got the row and column you just pop up q simple and this was a part of your bfs if you remember in the vfs algorithm you stored that into the vfs but now we are more concerned about just going and marking it right now we need to traverse in the neighbors travel in the neighbors and mark them if it's a land this is what we need to do now the question comes up you need to travel in its neighbors so which are its neighbors so i'm going to teach you a shortcut for this so apparently if you are standing at a row column let's let's come back to the ipad if you're standing at a row column which is kind of a portion now it will have a neighbor as the upper guy it will have a neighbor as this guy it will have a neighbor as this guy it will have a neighbor as this guy it will have a nipper as this guy this this and this so either you can write eight neighbors separately by writing eight different lines or there's a shortcut so this is row and this is column what will be the index above row that's going to be row minus 1 column right what with this this will be row minus 1 column plus 1 perfect this will be row comma column plus 1 perfect what will be this this will be row plus 1 column plus one perfect this will be row plus one comma column perfect this will be row plus one column minus one perfect this will be row comma column minus one perfect this will be row minus one column minus one perfect so if you carefully see everything is like minus one row how is rho varying minus one minus one or it's like row row row or it's like row plus one row plus one this portion is row plus one this is row and this is row minus one house column varying this is column column minus one and column plus one so everything is varying from minus one to plus one in both row and columns right so what you will do is you run a couple of loops and you can call it as delta i or something like this delta i or delta rho delta rho goes from minus 1 to plus 1 and similarly you can call delta column from -1 to plus 1 and this will now for the neighbors you can say the neighbor row is row plus delta rho and you can say the neighbor column is column plus delta column this will give you the neighbor row and the neighbor column very very easily why because first time it will be minus one this will be minus one so first time it will be like minus one minus one which does have next will be minus one and this will go to zero so minus one plus zero next time will be minus 1 and plus 1 so minus 1 plus 0 so you will actually come across every neighbor if you just follow this technique you don't have to write them individually you will automatically come across all of these neighbors right so let's go back to the code and now try to get all these neighbors so here like delta rho equal to minus 1 delta rho greater than equal to this right and then you say delta rho plus plus perfect and then what you do is delta column equal to minus one delta column less than equal to one and delta column plus plus perfect this is something which you have done neighbor row will be what row plus delta rho neighbor column will be what column plus del column now these guys have to be valid because if you remember they might nothing be on the top or they might be crossing boundaries so make sure the neighbor row is valid which is this again which is you need to make sure you need n and m so you can again just recompute them or you can carry them from them so great dot size and you can say great zero dot size will be your column six perfect so you can say this has to be valid thereby this has to be this and and obviously n column has to be greater than 0 and an n column has to be lesser than m this is for valid once they are valid they have to be very very important once they are valid they have to be uh water sorry a land which is something like this they have to be a land and was the next thing they have to be non-visited as well so the new row and the new column have to be non-visited as well so you need to make sure you write all these conditions yes you need to make sure you write all these conditions together like first you check for validity then you check for land and then you check for visited and if all of these are satisfied you can just go and do enroll n column equal to one that's visited and you can say the queue to please go and store the new row and then new column once this is done in this way you can traverse all the neighbors and you can just keep on doing the same bfs travis and once by the way just make sure this is land as well grid of row column has to be land as well in order to do a bfs traversal perfect so now what you can do is you can just go across and run the code and if you see the output is correct it does run fine and your task will be to probably try bfs sorry a dfs and the dfs traversal just make sure the these are the neighbors and everything else will stay the same so this is how you can easily use the bfs algorithm in something like a matrix in order to solve a particular problem so let's discuss the space complexity at first so what are we using we're using a visited matrix which is taking n square now a lot of you might argue that forever we can use the given like given matrix only to mark visited yes you can use that but generally uh even if you're using that in order to solve a problem you're using space you're using space so you're using big of n square space in order to have your visited stuff whether you do it on a grid or whether you separate uh create a separate error that doesn't matter but you're using big of n square space you can explain that to the interview and there is uh is there any other space uh there is a q space at max n square q uh space if all of these guys are connected the q might end up taking n square space but that will not happen uh that is a very very rare case that's not going to happen so um we can say the space complexity is near about big o of n square what about the time complexity we're running multiple loops like if you look at the code like it's n square over here and then you're calling bfs but if you are you won't be calling for every guy like you it is not possible that uh everyone is one and you call bfs for everyone that's not going to happen right so in in total you over here called bfs for once twice thrice uh like four times five times six times seven times eight times so it was kind of eight plus you traversed for n square plus n square is what you traverse like you've to find out this first one so it'll be like if everyone is marked as one if everyone is marked as one so the bfs will travel like n square nodes if everyone is marked as one the bfs will traverse n square nodes right and then there are neighbors that has like eight neighbors for everyone so you are going to check eight neighbors for everyone so n square nodes into eight neighbors is what you're checking so you're checking eight neighbors but you might argue what's right this will be running for like three into three nine times but out of that one time will be ignored why because when del row will be zero and l column will be zero it means the current row and column which is like it will be like row plus 0 and column plus 0 but you will find that as visited so it will not go there so apparently you're going for n square nodes and for every time you're finding nine neighbors or eight neighbors so it's like n square into nine and then you're traveling in the matrix so it's something like n square for the matrix in order to check for once and then you're doing a b of s like n square into nine so roughly n square you can call the complexity s so the time complexity will roughly boil down to n square if you want to go into deep you can just analyze it again and again you will be more confident about this so guys i hope i was able to make you understand this particular question because it has a lot of concepts but just in case you understood please please please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right away and yeah with this i will be wrapping up this video let's meet in some other video till then bye bye take care by the way sd sheet and the dp series the link are in the description please make sure you check them out bye take care whenever your heart forget is golden