Given an m x n 2d grid 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
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'.
The description was taken from https://leetcode.com/problems/number-of-islands/.
#O(M*N) Space, O(M*N) Time
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
def in_bounds(row:int, col:int) -> bool:
if row < 0 or col < 0 or row >= m or col >= n:
return False
if grid[row][col] == "0":
return False
return True
def dfs(row:int, col:int) -> None:
if not in_bounds(row, col):
return
grid[row][col] = "0"
dfs(row+1, col)
dfs(row-1, col)
dfs(row, col-1)
dfs(row, col+1)
count = 0
for row in range(m):
for col in range(n):
if grid[row][col] == "1":
dfs(row, col)
count += 1
return countSimilar to the other Island problems, we are looking for specific paths within a matrix. We aren't looking for the shortest path, or if a path exists. We are just looking for each path of connected ones surrounded by zeros.
With that in mind, a Depth-First Search is going to be our best bet for these types of problems although a Breadth-First Search could work also for this specific problem.
What we can do is traverse the grid and each time we see a one, we will stop and run a DFS to flip each one to a zero within that island and increment our counter once the island has sunk. That way, if we encounter another one in our traversal afterward, we will know that there is no way that one could have belonged to any previous island because it would have sunk along with it, so we can increment our count again.
This pattern falls in line with not only the other Island problems but the Number of Provinces and Number of Components in an Undirected Graph type problems as well.
Let's start by saving the caching the length and width of the graph into variables m and n, so that we don't have to keep recalculating these values later.
m, n = len(grid), len(grid[0])
Next, let's create a helper function for ourselves to help us know whether our DFS has gone out of bounds or not.
def in_bounds(row:int, col:int) -> bool:
This function will let us know if we have gone out of bounds of the matrix, or have hit the water. In either case, we aren't on land so we will return false.
if row < 0 or col < 0 or row >= m or col >= n:
return False
if grid[row][col] == "0":
return False
Otherwise, we will return True.
return True
Next, we will create our recursive, dfs function.
This function will take a row and a column for the cell our DFS will visit.
def dfs(row:int, col:int) -> None:
If our DFS has gone out of bounds, we will return from this path.
if not in_bounds(row, col):
return
Otherwise, we will sink this piece of island which will also let us know later not to revisit it and we will continue the DFS on our bottom, top, left, and right neighbors.
grid[row][col] = "0"
dfs(row+1, col)
dfs(row-1, col)
dfs(row, col-1)
dfs(row, col+1)
Now that we have our functions built, let's initialize our count and start our traversal through the sea.
count = 0
for row in range(m):
for col in range(n):
If we encounter a piece of land, we will halt our traversal and sink the island it belongs to then increment the count.
if grid[row][col] == "1":
dfs(row, col)
count += 1
As mentioned previously, if we come across another piece of land within the next iteration of our traversal, we can be sure that it is a new island because we just sank this one.
Once we have sunk and counted each island, we will return the count of islands we saw and sank.
return count