The number of islands is one of the most popular programming problems.
Read the problem description first.
Before getting into the solution, I assume you already know about the DFS algorithm. We will use this algorithm to solve this problem.
The four edges and ‘0’s will be counted as water in the given grid.
To solve this problem:
- We will go through every cell of the grid.
- If the cell value is 1, and it’s not already visited, we got a new island to add for the final result. If the cell is ‘0’, then ignore it.
- Now we will start visiting that cell and all the adjacent cells whose value is ‘1’ and label them as visited.
- We will do this using DFS. Remember, we will not traverse diagonally in the grid. And we won’t go further to search if there is an edge or water cell (0).
- We will check every cell like the previous way.
- After that, we will return the final result. The total number of islands.
Let’s see the following solution.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
visited = set()
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or (r, c) in visited or grid[r][c] == '0':
return
visited.add((r, c))
dfs(r+1, c)
dfs(r, c+1)
dfs(r-1, c)
dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r, c) not in visited:
dfs(r, c)
islands += 1
return islands