DFS
Depth-first search on a 2D grid treats each cell as a node, with edges to its 4 neighbors (up, down, left, right). Starting from any unvisited cell, DFS explores as far as possible before backtracking.
Connected Components
A connected component in a grid is a maximal set of cells that are all reachable from each other via adjacent moves.
200. Number of Islands
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def numIslands(grid):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return
if grid[row][col] != "1" or visited[row][col]:
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
islands_count = 0
for row in range(m):
for col in range(n):
if grid[row][col] == "1" and not visited[row][col]:
islands_count += 1
dfs(row, col)
return islands_count
419. Battleships in a Board
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def countBattleships(board):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return
if board[row][col] != "X" or visited[row][col]:
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(board), len(board[0])
visited = [[0] * n for _ in range(m)]
battleship_count = 0
for row in range(m):
for col in range(n):
if board[row][col] == "X" and not visited[row][col]:
battleship_count += 1
dfs(row, col)
return battleship_count
694. Number of Distinct Islands
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def numDistinctIslands(grid):
def dfs(row, col, direction):
if not (0 <= row < m and 0 <= col < n):
return
if not grid[row][col] or visited[row][col]:
return
visited[row][col] = 1
path.append(direction)
dfs(row + 1, col, "D")
dfs(row, col + 1, "R")
dfs(row - 1, col, "U")
dfs(row, col - 1, "L")
path.append("B")
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
island_signature = set()
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
path = []
dfs(row, col, "S")
island_signature.add(tuple(path))
return len(island_signature)
733. Flood Fill
Easy1 solutionanalysis1 playground
Solutions:
Analysis
def floodFill(image, sr, sc, color):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return
if image[row][col] != original_color or visited[row][col]:
return
image[row][col] = color
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(image), len(image[0])
visited = [[0] * n for _ in range(m)]
original_color = image[sr][sc]
dfs(sr, sc)
return image
1034. Coloring A Border
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def colorBorder(grid, row, col, color):
def dfs(r, c):
if not (0 <= r < m and 0 <= c < n):
return
if grid[r][c] != original_color or visited[r][c]:
return
visited[r][c] = 1
if (
r == 0
or r == m - 1
or c == 0
or c == n - 1
or grid[r - 1][c] != original_color
or grid[r + 1][c] != original_color
or grid[r][c - 1] != original_color
or grid[r][c + 1] != original_color
):
borders[r][c] = 1
dfs(r + 1, c)
dfs(r, c + 1)
dfs(r - 1, c)
dfs(r, c - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
borders = [[0] * n for _ in range(m)]
original_color = grid[row][col]
dfs(row, col)
for r in range(m):
for c in range(n):
if borders[r][c]:
grid[r][c] = color
return grid
463. Island Perimeter
Easy1 solutionanalysis1 playground
Solutions:
Analysis
def islandPerimeter(grid):
def dfs(row, col):
nonlocal perimeter
if not (0 <= row < m and 0 <= col < n):
return
if not grid[row][col] or visited[row][col]:
return
visited[row][col] = 1
land_neighbors = sum(
1
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]
if 0 <= row + dr < m and 0 <= col + dc < n and grid[row + dr][col + dc]
)
perimeter += 4 - land_neighbors
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
perimeter = 0
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
dfs(row, col)
return perimeter
return perimeter
695. Max Area of Island
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def maxAreaOfIsland(grid):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return 0
if not grid[row][col] or visited[row][col]:
return 0
visited[row][col] = 1
return (
1
+ dfs(row + 1, col)
+ dfs(row, col + 1)
+ dfs(row - 1, col)
+ dfs(row, col - 1)
)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
max_area = 0
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
max_area = max(max_area, dfs(row, col))
return max_area
3619. Count Islands With Total Value Divisible by K
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def countIslands(grid, k):
def dfs(row, col):
nonlocal total
if not (0 <= row < m and 0 <= col < n):
return
if not grid[row][col] or visited[row][col]:
return
visited[row][col] = 1
total += grid[row][col]
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
islands_count = 0
total = 0
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
total = 0
dfs(row, col)
islands_count += total % k == 0
return islands_count
1254. Number of Closed Islands
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def closedIsland(grid):
def dfs(row, col):
nonlocal is_border
if not (0 <= row < m and 0 <= col < n):
is_border = True
return
if grid[row][col] != 0 or visited[row][col]:
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
count = 0
for row in range(m):
for col in range(n):
if grid[row][col] == 0 and not visited[row][col]:
is_border = False
dfs(row, col)
count += not is_border
return count
1905. Count Sub Islands
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def countSubIslands(grid1, grid2):
def dfs(row, col):
nonlocal is_sub_island
if not (0 <= row < m and 0 <= col < n):
return
if grid2[row][col] != 1 or visited[row][col]:
return
visited[row][col] = 1
if grid1[row][col] == 0:
is_sub_island = False
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid2), len(grid2[0])
visited = [[0] * n for _ in range(m)]
sub_islands_count = 0
for row in range(m):
for col in range(n):
if grid2[row][col] == 1 and not visited[row][col]:
is_sub_island = True
dfs(row, col)
sub_islands_count += is_sub_island
return sub_islands_count
827. Making A Large Island
Hard1 solutionanalysis1 playground
Solutions:
Analysis
def largestIsland(grid):
def dfs(row, col, iid):
if not (0 <= row < m and 0 <= col < n):
return
if not grid[row][col] or visited[row][col]:
return
visited[row][col] = iid
island_size[iid] = island_size.get(iid, 0) + 1
dfs(row + 1, col, iid)
dfs(row, col + 1, iid)
dfs(row - 1, col, iid)
dfs(row, col - 1, iid)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
island_size = {}
island_id = 0
largest_island = 0
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
island_id += 1
dfs(row, col, island_id)
for row in range(m):
for col in range(n):
if not grid[row][col]:
neighbor_ids = set()
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
if 0 <= row + dr < m and 0 <= col + dc < n:
neighbor_ids.add(visited[row + dr][col + dc])
largest_island = max(
largest_island, sum(island_size.get(i, 0) for i in neighbor_ids) + 1
)
return largest_island or m * n
Surrounded Regions
130. Surrounded Regions
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def solve(board):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return
if board[row][col] != "O":
return
board[row][col] = "B"
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(board), len(board[0])
for row in range(m):
dfs(row, 0)
dfs(row, n - 1)
for col in range(n):
dfs(0, col)
dfs(m - 1, col)
for row in range(m):
for col in range(n):
if board[row][col] == "B":
board[row][col] = "O"
elif board[row][col] == "O":
board[row][col] = "X"
417. Pacific Atlantic Water Flow
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def pacificAtlantic(heights):
def dfs(row, col, visited, prev_height):
if not (0 <= row < m and 0 <= col < n):
return
if visited[row][col] or heights[row][col] < prev_height:
return
visited[row][col] = 1
dfs(row + 1, col, visited, heights[row][col])
dfs(row, col + 1, visited, heights[row][col])
dfs(row - 1, col, visited, heights[row][col])
dfs(row, col - 1, visited, heights[row][col])
m, n = len(heights), len(heights[0])
pacific = [[0] * n for _ in range(m)]
atlantic = [[0] * n for _ in range(m)]
for row in range(m):
dfs(row, 0, pacific, 0)
dfs(row, n - 1, atlantic, 0)
for col in range(n):
dfs(0, col, pacific, 0)
dfs(m - 1, col, atlantic, 0)
results = []
for row in range(m):
for col in range(n):
if pacific[row][col] and atlantic[row][col]:
results.append([row, col])
return results
1020. Number of Enclaves
Medium1 solutionanalysis1 playground
Solutions:
Analysis
def numEnclaves(grid):
def dfs(row, col):
if not (0 <= row < m and 0 <= col < n):
return
if not grid[row][col] or visited[row][col]:
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
for row in range(m):
dfs(row, 0)
dfs(row, n - 1)
for col in range(n):
dfs(0, col)
dfs(m - 1, col)
count = 0
for row in range(m):
for col in range(n):
if grid[row][col] and not visited[row][col]:
count += 1
return count