Skip to main content

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​

200. Number of Islands

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

419. Battleships in a Board

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

694. Number of Distinct Islands

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

733. Flood Fill

Easy1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

1034. Coloring A Border

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

463. Island Perimeter

Easy1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

695. Max Area of Island

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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:

Traced Engine

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​

1254. Number of Closed Islands

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

1905. Count Sub Islands

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

827. Making A Large Island

Hard1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

130. Surrounded Regions

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

417. Pacific Atlantic Water Flow

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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​

1020. Number of Enclaves

Medium1 solutionanalysis1 playground
Solutions:

Traced Engine

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