200. Number of Islands
# O(n * m) time || O(n * m) space
def num_islands_dfs(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
def dfs(i, j):
if 0 <= i < n and 0 <= j < m and grid[i][j] == "1":
grid[i][j] = "0"
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
res += 1
dfs(i, j)
return res
# O(n * m) time || O(n * m) space
def num_islands_dfs_shorter(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
def dfs(i, j):
if 0 <= i < n and 0 <= j < m and grid[i][j] == "1":
grid[i][j] = "0"
list(map(dfs, [i - 1, i + 1, i, i], [j, j, j - 1, j + 1]))
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
res += 1
dfs(i, j)
return res
# O(n * m) time || O(min(n, m)) space
def num_islands_bfs(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(i, j):
dq = collections.deque([(i, j)])
while dq:
x, y = dq.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == "1":
grid[nx][ny] = "0"
dq.append((nx, ny))
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
res += 1
bfs(i, j)
return res
This problem is a classic example where Depth First Search (DFS) can be used. Every time we find a “1”, we start a DFS traversal to mark all the connected “1"s. Every island will initiate exactly one DFS traversal. Therefore, by counting how many times DFS is called, we can find out the number of islands.
Here’s how the algorithm works:
- Loop through each cell in the grid.
- If the cell value is “1”, increment our island counter and start a DFS traversal from that cell.
- Within the DFS traversal, mark the visited cell as “0” (water) to ensure we don’t visit it again.
- Visit the 4 possible directions from the current cell (top, bottom, left, right). If we find a cell with value “1”, continue the DFS traversal from that cell.
- Once we have visited all the cells of an island using DFS, return to the main loop and continue checking the next cell.