Leetcode 200 : Number of Islands
Reading Time : 10 minutes
Day 6/30.
Disclaimer : There are multiple ways to solve a problem, this just happens to be my favorite and the one that comes most naturally to me!
I don’t know why I thought there will be another topic which will get more interest than LeetCode when I asked for things you will like to read about. 🤷🏻♀️ If you are on this page, you are probably a computer science student, or currently preparing for interviews. Either way, welcome to the first of many leetcode questions you will see in the future on this website. If you’ve read my interview preparation post, you know that I love LeetCode as a platform to practice but I hate the solutions. Over the last year or so, I have developed my own method of solving interview questions and it has worked well for me. It is time to share it here with all of you.
Leetcode 200 : Number of Islands
The reason that I chose this to be the first problem I solve here is that companies love this problem! It is one of the most frequently asked interview questions, very highly rated and well, I personally love this question. I was also asked to solve this problem in 2 of my internship interviews (yes, that’s right!!)! It is able to test your problem-solving skills (can you convert a real-life problem into an algorithmic problem), algorithms knowledge (can you write code for that algorithm) and it also has some aspects of object-oriented design.
So here is the problem:
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.
The single most important thing when trying to solve a problem like this is to make sure that you understand the inputs and outputs correctly. Here is a quick video that explains how to understand this problem:
That actually concludes the first step I use while trying to understand a problem - understand the input and output as much in depth as possible because that will guide which algorithm I will use to solve the problem.
Now, solving the problem manually like that - from input to the output - makes me question what data structures and algorithms do I know which can help to work on this problem. We are essentially trying to find “1”s which are connected to each other.
I have a “1” (a) - is it connected to any other “1”s? Yes - so I can go to that “1”(b) and then see if (b) is connected to any other “1”s
This definitely gives me an idea that a recursive solution might be the easiest way to go about solving this question, because we are trying to repeat the same step again and again every time we encounter a “1”. [Now I know everyone is not comfortable with recursion and I was one of those people myself, but with enough practice, it starts coming to you naturally.]
Another thing that I notice is that an island starts when I encounter a “1”. The 0s are of no use to me - so if I do a linear scan of the grid:
When I encounter a “1”, I can increase the number of islands by 1
Now I need to make sure that all the “1”s connected to my starting “1” don’t get re-counted. Since 0s are of no use to me, I can make all of the connected “1”s equal to 0.
Current solution in my head :
Do a linear scan of the grid for a “1”.
Recursively find all the “1”s connected to each other at this step, and make them 0 to avoid recounting
Starting with islands = 0 :
# linear scan for r in range(rows): for c in range(columns): if grid[r][c] == "1": islands += 1 # when I encounter 1, number of islands increase recursive_func(grid, r, c)
What will my recursive function look like?
def recursive_func(grid, r, c): grid[r][c] = 0 # change 1s to 0 so that they don't get recounted # we want to include all 1s which are connected horizontally and vertically # So starting at position (r,c), horizontal connections become (r, c+1) and (r, c-1) where as vertical connections become (r+1, c) and (r-1, c) if grid[r+1][c] == "1": recursive_func(grid, r+1, c) if grid[r-1][c] == "1": recursive_func(grid, r-1, c) if grid[r][c+1] == "1": recursive_func(grid, r, c+1) if grid[r][c-1] == "1": recursive_func(grid, r, c-1)
Now I have a structure for my solution, I go over the entire grid, find a “1”, increase the number of islands by 1, recursively find all the other “1”s & change them to “0” if found. The next thing I ask myself is if I have missed any edge cases. In this case, there “literally” is an edge of the grid that you can’t go over and if you do, there will be an error. So I need to check for boundary conditions in my recursivefunc ( 0 <= r < rows and 0 <= c < columns). The other edge case to always check if the input is empty (so if the grid is []).
If you haven’t realized by now, we are essentially doing a depth-first search (DFS) on the grid. The grid can be thought of as a collection of nodes, each with a value of 0 or 1. If a node contains a “1”, then it is a root node that triggers a DFS. During DFS, every visited node should be set as “0” to mark as visited node. Count the number of root nodes that trigger DFS, this number would be the number of islands since each DFS starting at some root identifies an island. So the entire code really becomes of the DFS pseudocode and changes you need are 1) add a part to count number of islands 2) change 1s to 0s once visited. Here it is:
def numIslands(self, grid: List[List[str]]) -> int: rows = len(grid) if rows == 0: # empty input? return 0 columns = len(grid[0]) islands = 0 # keeping track of output def dfs(grid, r, c): # recursive function grid[r][c] = 0 # change "1" to 0 if r >= 0 and r+1 < rows and grid[r+1][c] == "1": dfs(grid, r+1, c) if r-1 >= 0 and r-1 < rows and grid[r-1][c] == "1": dfs(grid, r-1, c) if c >= 0 and c+1 < columns and grid[r][c+1] == "1": dfs(grid, r, c+1) if c-1 >= 0 and c-1 < columns and grid[r][c-1] == "1": dfs(grid, r, c-1) # linear scan for r in range(rows): for c in range(columns): if grid[r][c] == "1": islands += 1 dfs(grid, r, c) return islands
It is a little difficult to walk through the correctness of this algorithm in a written post, and until I can gather the courage to make videos, maybe that is the next skill I need to master! The last thing that we need to discuss is the time and space complexity of using this solution.
At the very most, we need to go over the entire grid during the linear scan so the time complexity will be in the order of O(rows * columns). We are not using any extra space in the solution but don’t forget the stack used during the DFS recursion. Maximum stack size will be O(rows * columns) and so that is the space complexity of this solution.
This concludes my first Leet Code Post! Let me know in the comments below if you have any questions and the next problem that you would like me to walk through here! And while you’re here, go subscribe to my YouTube channel if you would like to see more videos :) Thank you!
