[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.
Step 3: Finishing the Optimal Solution
How can we improve our solution? The basic structure of BFS/DFS can’t really be changed too much. But this is where understanding the algorithms comes in handy.
We normally keep a visited set, because we can’t afford to change the input as we will need to use it in other situations. In our case, however, we only care about the number of islands. Thus we can change our grid, as long as we do it in a sensible way.
Notice our traversal algorithms get triggered only when we hit locations of value 1. Thus an easy way to make sure that we don’t trigger our traversal for already visited land locations is to simply mark them as visited. Instead of having a separate data structure, we can modify our grid in place. This will reduce the memory we need to use significantly.
Some of you might be nervous about doing this. Aren’t we messing up the fundamental structure of the grid? This is where the recursive structure discussed displays itself. Remember that whether an island is [1] or [1,1,1,1] it is still one island. Thus, we can change all the values adjacent to our first traversal trigger safely. We want to be careful of changing any 0s or forgetting to change any visited locations however.
Step 4: Code
The code is a relatively straightforward implementation of your traversal algorithm. I went with DFS because the recursion would be done very quickly (we have very few steps in the recursion steps). Thus, I figured that the performance in practice would be very speedy. My deduction was correct.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid: return 0
rows = len(grid)
cols = len(grid[0])
num_islands = 0
def dfs(r,c):
grid[r][c] = '#'
if(r+1 < rows and grid[r+1][c] == '1'): dfs(r+1,c)
if(c+1 < cols and grid[r][c+1] == '1'): dfs(r,c+1)
if(r-1 >= 0 and grid[r-1][c] == '1'): dfs(r-1,c)
if(c-1 >= 0 and grid[r][c-1] == '1'): dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
num_islands += 1
dfs(r, c)
return num_islandsNotice that immediately mark all 1s before we process anything. This is just something I do to ensure that nothing is missed. It’s more of a design philosophy than a hard and fast rule. I would suggest always doing the critical things you have to do in your function first, so you don’t have to worry about them.
Time Complexity- O(m*n) since we work through the entire grid. We have no choice
Space Complexity- O(m*n). The recursion would in the worst case store all the stack frames. However, because the recursion would end so quickly, this would not happen in practice. This is why my memory consumption is still lower than most solutions presented.
Make sure you share your thoughts on this question/any interesting questions/developments in the comments or through my links.
Happy Prep. I’ll see you at your dream job.
Interview Ace,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75