Today's problem is a pretty common interview question on Leetcode called Number Of Islands.
The Question
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 Approach
I'll be honest, I did not immediately jump to thinking of using a Depth-First Search for this problem. I initially thought of the brute force approach of iterating through each element in the grid, and keeping track of all adjacent elements in some other data structure. I had learned about both DFS and BFS in the context of graphs and trees, so it didn't instantly click that a DFS or BFS algorithm would be appropriate here.
Once I landed on using a DFS algorithm, I needed to figure out how to make it applicable to this particular problem. I knew I'd want to start in the upper-left corner of the grid (at coordinates 0, 0), and do something once I encountered a grid space that equaled 1. If we encounter a grid space that equals 1, then we know we've hit an island, and we'll need to explore the surrounding grid elements to see just how large this island is.
The rough, overall plan of attack is to iterate through our grid, and whenever we find a '1', flip the '1' to a '0' and then run DFS on all adjacent spaces until we've exhausted the entire grid. Running DFS recursively using a starting space that equals 1 should allow us to obtain the 'total size' of the island, which we could then use to actually keep a running count of the total number of islands.
The Solution
Almost always, the first thing I'll do before diving into the meat of the algorithm is to think of possible edge cases. I usually don't catch all of them at this stage, but the usual edge cases I'll write first is if the input is 0, empty, null, None, etc.
def num_islands(grid: List[List[str]]) -> int:
# variable to hold the number of islands
island_count = 0
# first check if there are values in the grid
if not grid:
return island_count
Next, I want to set the grid length and width, to ensure that my solution will never reach out of bounds. I'll do this by setting m and n, respectively.
# m will represent the number of rows in our grid
m = len(grid)
# n will represent the number of columns in our grid
n = len(grid[0])
Now that I've got my boundaries all squared away, it's time to move onto the meat of the solution -- writing a Depth-First Search algorithm. There are plenty of great resources online with explanations and code samples of a DFS, ranging from GeeksforGeeks, basecs and more, so I won't go over the details here.
def dfs(i, j):
# check if i and j are still on the grid
# check if the current spot doesn't already equal 1
if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
return
# otherwise
else:
# set current grid space to 0
grid[i][j] = 0
# run dfs on all surrounding elements
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
I am using a helper function to implement the DFS, and the function will accept parameters i and j that represent a current grid coordinate. Let's say we encounter our first '1' at (3, 2), we would then call dfs(3, 2).
Right off the bat we'll check if the position is valid, and check that the current spot doesn't already equal 1. If any of those cases are true, we can return out early. We then need to check if the grid space is 0 (meaning it is a water space) we can also exit out of the function.
Otherwise, the current grid space must be equal to '1', so we will flip that to a '0' and recursively call our dfs helper function on all adjacent elements (up, down, left, right).
Honestly, at this point, most of the hard work is over! 🎉 We just need to write the code to iterate through the grid and identify those 1's!
# initial for loop to iterate through the grid
for i in range(m):
# iterating through each row
for j in range(n):
# if current grid space is 1
if(grid[i][j] == "1"):
# increment island count
island_count += 1
# run dfs using the current spot as the root
dfs(i, j)
# if grid space is 0
else:
# continue searching
continue
# return count when done
return island_count
Here it is, in it's final form!
def num_islands(grid: List[List[str]]) -> int:
# variable to hold the number of islands
island_count = 0
# first check if there are values in the grid
if not grid:
return island_count
# set the lengths:
# m represents the number of rows
m = len(grid)
# n represents the number of columns
n = len(grid[0])
# definition of depth-first search
def dfs(i, j):
# check if i and j are still on the grid
# check if the current grid spot doesn't already equal 1
if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
return
# otherwise
else:
# set current grid space to 0
grid[i][j] = 0
# run dfs on all surrounding elements
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
# initial for loop to iterate through the grid
for i in range(m):
# iterating through each row
for j in range(n):
# if current grid space is 1
if(grid[i][j] == "1"):
# increment island count
island_count += 1
# run dfs using the current spot as the root
dfs(i, j)
# if grid space is 0
else:
# continue searching
continue
# return count when done
return island_count
The Complexity
The time complexity for this implementation is O(mn), where m is the number of rows in our grid and n is the number of columns.
Top comments (0)