Hey everyone, glad to finally get this tutorial out to you all. I know I’ve been stating this for months now but I finally re-visited the question the other day and it was a lot less intimidating than when I had first seen the algorithm last year. I hope to simplify it for you all. It is not an easy question for most, so please be patient with yourself and take your time. This isn’t a problem you can rush to understand. Especially, if you are new to algorithms. Enjoy!
*BFS version now available! Scroll to the bottom. I have a recursive and iterative function.
If you do not know what Depth First Search algorithm is, or you need a refresher. Watch this video by another Youtuber. We will be using this algorithm to solve the problem.
The Number of Islands question can be found on LeetCode. I’m not sure if it was originally created there, as I heard about the problem from another person. Here is the prompt:
“Given a 2d grid map of
'1's (land) and
'0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.”
Here is the full code first:
Here we have our graph/grid/matrix/2d array (call it what you want). After solving the algorithm, we should come up with a value of 3. Why? Because there are only 3 islands. We count an island based on the 1’s and one island would count as either one 1, if it surround by all 0’s (water), or one island if there is a 1 and all other 1’s surrounding it are either adjacent or above/below. We do not count diagonals.
Here, we have our main algorithm that keeps track of our island count. We give it an argument, “graph”, which represents the graph above. Next, is an edge case. Here we return 0 if there is no graph or you can raise an error stating that one can not use an empty graph. The next two lines are our row and col. We save the length of rows of the graph above, 4, as well as the number of columns in the graph, 5. Remember, rows are horizontal and columns are vertical. I explain in further detail in the video below. Lastly, we set a variable, count, to 0 to track the number of islands found.
Next, we have our nested for loops. Whenever you see a 2d array and you need to grab rows and columns think of this. The first for loop grabs the rows (4 of them) starting at index 0. What range is saying is that we will loop from 0-4. The second for loop is an amazing way to grab the columns and values. The second for loop will check if the graph equals 1 (island). If it does, it will call our second function, dfs(), to do the depth first search. Once we’ve exited the recursive function, we will increment count by 1. Finally, we return the count/number of islands.
Below, we have our function to do the DFS. As you may have noticed, there are two new values, x and y. Those are a substitute for i and j as we do not want to get confused. You can make them anything. Their values will be the same as i and j regardless. The second line of code checks to see if the value we are on at the moment is 0. If it is, the program returns to the previous function or the last if statement (as you will see further on). This problem is recursive. If the value we are on is 1, we turn it into 0, just so that we know it has been visited. There is no need to count the amount of 1’s we see because once we’ve returned to the numIslands function, we would’ve already incremented by 1.
Now, the meat of the algorithm. The first if statement checks to see if we are on the first row or not. If we are, then it moves on. graph to graph is the first iteration for i, so we will be passing this statement as, graph[x-1][y], looks for the value above itself, to check if it is also a 1. Remember, we can only look above, below, left and right. If we are on the first row, it is not possible to look at values above us. This is the same logic with the second if statement. The second statement checks to see if we are on the last row of the graph. If we are on the last row, we can not check any values below us because there aren’t any.
However, since we are on the first iteration graph, we can check below us, graph. Remember, graph is the second row, and graph is still in the first column. We see here that graph equals “0” so we return as with the second and third lines in dfs() above.
Once we’ve returned, we are back at square one, graph and now want to look to the left of us to see if there are any 1’s. As with the two if statements above, the two if statements below check to see if we are in the first and last columns of the graph. If we are in the first column, we can not look to the left as there is nothing before us, so we skip that if statement here. The last if statement we satisfy, as we are not in the last column, therefore we are able to look to our right.
graph equals “1”! So we move to the second column, but we are still in the first row, and 0 out the value, “1”, as visited. Then we begin the entire process again. We look down, but we cannot look above as we are still in the first row. We see that graph also equals “1”! So we move on to there and 0 it out as well. Once we’ve checked left, right, up and down we see there are no more 1’s so we return to the previous value, graph. graph finishes what it started and looks to the right only to see “0” and returns back to graph, which had already looked everywhere it could and returns/exits the dfs() function to increment count += 1 in numIslands().
Feel free to watch the video version of this post below. It may or may not be more beneficial to you. 🙂
Breadth First Search!
So, I have two versions for you. I’m only going to break down one (with comments in code), and i’ll let you figure out the other. Just be patient, you’ll get it. Also note that I dug through the mud for these solutions online. There are various forms of these implementations. A few want you to import collections. These do not require that. I did not come up with both of them entirely. I made several adjustments to be more understandable for you.
For this example, we are changing all 1’s that we encounter, to a 2.
The for loop below is in line with everything above.
The while loop is in line with the graph[i][j]= 2. It is under both for loops.
The If statements below are in line with those above.
Anotha one 🙂
If after reading this post and watching my explanation you are still confused, do not panic. Hop over to my favorite site to visualize algorithms, pythontutor.com, to get a better breakdown of what is going on.