Solving Number of Islands using Depth First Search (DFS)
As a continuation of our code challenge practice, we will be solving a common problem called Number of Islands using a graph traversal technique called Depth First Search (DFS, going forward).
Problem Setup:
We have a m x n grid represented by the nested array above. The 1s represent landmasses and 0s are the ocean. A landmass is considered to be 1s that are adjacent horizontally or vertically but not diagonally. Given a grid similar to the one above, return the number of islands.
DFS Approach:
Intuition tells us that the above problem can be thought of as an undirected graph and there are edges either horizontally or vertically between nodes that have a value of 1.
We are going to scan through the graph, from left to right, top to bottom, and every time we hit a value of 1 we trigger a DFS function. This function will change the value of the current node to 0 to mark it as visited. The function will also recursively check the horizontal and vertical neighbors. Before we trigger the function we increase a counter variable as the DFS will eliminate the entire landmass before our scan moves through the remaining part of the graph.
The basic gist of our algorithm is that each time we come across a 1 we will increment the island counter, invoke our DFS which checks for the entire landmass, and converts each node with a value of 1 to 0.
I think a key take on this problem is understanding our DFS function. The problem specifically stated vertical and horizontal neighbors. So in our DFS function, we will do 3 major steps:
- Define the base case to break out of our recursive approach
- The ‘work’ required, in this case converting the ‘1’ to a ‘0’
- Making 4 recursive function invocations to the 4 adjacent directions.
DFS Function:
I declared a few variables, islands as my counter along with maxRows and maxColumns. These variables are used to determine the boundaries of the graph. If we break down the base of our DFS function it is basically ensuring that our function is not searching out of bounds and that the specific node we are looking at is a landmass, otherwise, we end the recursive call.
If the conditions in the base case aren’t met then we know that we are on a viable part of a ‘landmass’ and we can perform the work of converting it to an ocean tile.
Finally, as said above we recursively call the DFS function with inputs that checks the 4 surrounding directions. This was a key point in the instructions that said we had to check the vertical and horizontal neighbors.
Iterating through the 2D array:
Now that we have our DFS function we simply iterate through the array and if we come across a node value of 1 we increment our island counter and activate the DFS function to convert the entire landmass to ocean tiles.
We simply return the counter to get the number of landmasses in our input.
Conclusion:
I came across this problem and wanted to share the solution I had come to because this problem is a lot to digest at first. You have to come to the realization that it’s a graph traversal problem, DFS or BFS (breadth-first search) are both viable traversing techniques for this problem. Then you have to logically think about how you want to set up your recursive function and what the base case should be. Coming to the realization that all you are doing is counting the instances where you invoke your DFS function is the culmination of all these smaller problems.
This resource from Visualgo is great if you want to visualize graph traversal and need to brush up on DFS / BFS concepts.
Thanks for taking the time to go through this problem with me and here’s the code for anyone who wants to play around with it!
