[Solution]Problem 33: Number of Islands[Spotify]
Graphs, Traversal, DFS, Data Structures Manipulation, BFS
This question is very interesting because it can be solved in multiple ways. I will be sharing my approach now. As you can see, it performs well, even compared to the other solutions shared online.
Problem
Given an m x n
2D binary grid grid
which represents a map of '1'
s (land) and '0'
s (water), return 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.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below -
Step 1: Understanding the Structure.
To build any efficient solution, it is important to first understand the structure of the problem given to us. That way, we can quickly infer what is expected and build out the solution from there.
One thing that immediately stands out to me is that the structure of the problem stays the same, regardless of the size of the islands. Whether I have giant islands, small islands, multiple islands, or only one, the way of finding whether two pieces of land are connected, etc stays the same. This is a hint, that our solution will be recursive (iteration is considered a kind of recursion in theoretical Computer Science). We should keep this in the back of our minds. We have a great step by step plan for building recursive solutions here.
For the more advanced among you, it will be clear that we will be treating this problem as a graph. To confirm this, I will be using the graph spotting framework we developed in our Math Mondays-
Entities- The entities will be the locations on the grid. That is intuitive. Everything depends on how the locations (0s and 1s) are laid out.
Relationships- Here two nodes are related if they are adjacent. We know the conditions for adjacency from the question description.
Weighted?- In our case, any two adjacent nodes will be identical in all ways. Thus clearly, we will be using unweighted graphs. This also narrows our scope to either BFS or DFS for traversal.
As you can see, having our framework made the identification of structure very easy. By combining practice and a theoretical foundation, results are inevitable. So make sure you check in for the other days when we discuss Math, Techniques, System Design, and much more. Coding Interviews are a multi-headed beast.
We now have a logical next step. How do we traverse the graph to create our solution? Let’s look into it.
Step 2: Figuring out the nuances of traversal
We generally have two choices when we approach Graph Traversal. BFS or DFS. Let’s see if we can look at the problem and figure out what we will be covering.
The first thing that stands out to me is that we will be visiting all the nodes of the graph. That is how we figure out the paths. Another important thing to notice is that the order in which we visit nodes doesn’t really matter.
This gives us a rare situation, where both traversal algorithms would work. Let’s look at the basic algorithm for how we could develop each-
DFS Algorithm
Scan the grid from (0,0) till (N, M).
If the current location is ‘1’, and our location hasn’t already been visited, start a DFS.
In the DFS traversal, mark every visited node.
Count the number of islands as the number of nodes that trigger the DFS.
Return count.
BFS Algorithm
Scan the grid from (0,0) till (N, M).
If the current location is ‘1’, and our location hasn’t already been visited, start a BFS.
Consider a queue and put the current node into the queue.
Iteratively visit its neighbors vertically and horizontally and mark them as visited.
The count is the total number of times the BFS has been invoked.
Return count.
Our algorithms are remarkably similar. This is one of the reasons I shared this question. It is a great question to practice both the graph algorithms and sharpen your skills.
In both algorithms, we always track the locations we visit. This is to avoid repeated work, which could lead to infinite loops. Typical BFS and DFS implementations have a visited set, that tracks the locations we visit.
Now we could finish the solution here. Either traversal would be perfectly acceptable. However, there is an optimization we can make, that will cut down the costs of the algorithm. It relies on understanding a fundamental point about the question.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.