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

Medium1 solutionanalysis

200. Number of Islands​

Solutions:

Interactive Visualization

Analysis

def numIslands(self, grid: List[List[str]]) -> int:
def dfs(row, col):
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(row, col):
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda i, j: visited[i][j]
isIsland = lambda i, j: grid[i][j] == "1"
islands_count = 0
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
islands_count += 1
dfs(row, col)
return islands_count

419. Battleships in a Board

Medium1 solutionanalysis

419. Battleships in a Board​

Solutions:

Interactive Visualization

Analysis

def countBattleships(self, board: List[List[str]]) -> int:
def dfs(row, col):
if not isValidCell(row, col):
return
if not isBattleship(row, col) or isVisited(row, col):
return
visited[row][col] = 1
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda i, j: visited[i][j]
isBattleship = lambda i, j: board[i][j] == "X"
battleship_count = 0
 
m, n = len(board), len(board[0])
visited = [[0] * n for _ in range(m)]
for row in range(m):
for col in range(n):
if isBattleship(row, col) and not isVisited(row, col):
battleship_count += 1
dfs(row, col)
return battleship_count

694. Number of Distinct Islands

Medium1 solutionanalysis

694. Number of Distinct Islands​

Solutions:

Interactive Visualization

Analysis

def numDistinctIslands(self, grid: List[List[int]]) -> int:
def dfs(row, col, direction):
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(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") # important
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for i in range(m)]
island_signature = set()
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda row, col: visited[row][col]
isIsland = lambda row, col: grid[row][col]
 
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
path = []
dfs(row, col, "S")
island_signature.add(tuple(path))
return len(island_signature)

733. Flood Fill

Easy1 solutionanalysis

733. Flood Fill​

Solutions:

Interactive Visualization

Analysis

def floodFill(
self, image: List[List[int]], sr: int, sc: int, color: int
) -> List[List[int]]:
def dfs(row, col):
if not isValidCell(row, col):
return
if not matchesOriginalColor(row, col) or isVisited(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]
 
matchesOriginalColor = lambda row, col: image[row][col] == original_color
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda row, col: visited[row][col]
 
dfs(sr, sc)
 
return image

1034. Coloring A Border

Medium1 solutionanalysis

1034. Coloring A Border​

Solutions:

Interactive Visualization

Analysis

def colorBorder(
self, grid: List[List[int]], row: int, col: int, color: int
) -> List[List[int]]:
def dfs(row, col):
if not isValidCell(row, col):
return
if not matchesOriginalColor(row, col) or isVisited(row, col):
return
visited[row][col] = 1
if isBorder(row, col):
borders[row][col] = 1
 
for r, c in directions:
dfs(row + r, col + c)
 
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]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
isVisited = lambda row, col: visited[row][col] == 1
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
matchesOriginalColor = (
lambda row, col: isValidCell(row, col) and grid[row][col] == original_color
)
isBorder = lambda row, col: any(
not matchesOriginalColor(row + r, col + c) for r, c in directions
)
 
dfs(row, col)
 
for row in range(m):
for col in range(n):
if borders[row][col] == 1:
grid[row][col] = color
 
return grid

463. Island Perimeter

Easy1 solutionanalysis

463. Island Perimeter​

Solutions:

Interactive Visualization

Analysis

def islandPerimeter(self, grid: List[List[int]]) -> int:
def dfs(row, col):
nonlocal perimeter
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(row, col):
return
visited[row][col] = 1
perimeter += 4 - neighbors(row, col)
 
for r, c in directions:
dfs(row + r, col + c)
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
perimeter = 0
 
isVisited = lambda row, col: visited[row][col]
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isIsland = lambda row, col: isValidCell(row, col) and grid[row][col]
neighbors = lambda row, col: sum(isIsland(row + r, col + c) for r, c in directions)
 
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
dfs(row, col)
return perimeter

695. Max Area of Island

Medium1 solutionanalysis

695. Max Area of Island​

Solutions:

Interactive Visualization

Analysis

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(row, col):
return
visited[row][col] = 1
areas[-1] += 1
 
for r, c in directions:
dfs(row + r, col + c)
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
areas = [0]
 
isVisited = lambda row, col: visited[row][col]
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isIsland = lambda row, col: grid[row][col]
 
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
areas.append(0)
dfs(row, col)
return max(areas)
Medium1 solutionanalysis

3619. Count Islands With Total Value Divisible by K​

Solutions:

Interactive Visualization

Analysis

def countIslands(self, grid: List[List[int]], k: int) -> int:
def dfs(row, col):
nonlocal total
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(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)
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda i, j: visited[i][j]
isIsland = lambda i, j: grid[i][j] > 0
islands_count = total = 0
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
total = 0
dfs(row, col)
islands_count += total % k == 0
return islands_count

1254. Number of Closed Islands

Medium1 solutionanalysis

1254. Number of Closed Islands​

Solutions:

Interactive Visualization

Analysis

def closedIsland(self, grid: List[List[int]]) -> int:
def dfs(row, col):
nonlocal isBorder
if not isValidCell(row, col):
isBorder = True
return
if not isLand(row, col) or isVisited(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
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isLand = lambda row, col: grid[row][col] == 0
isVisited = lambda row, col: visited[row][col]
 
for row in range(m):
for col in range(n):
if isLand(row, col) and not isVisited(row, col):
isBorder = False
dfs(row, col)
count += not isBorder
return count

1905. Count Sub Islands

Medium1 solutionanalysis

1905. Count Sub Islands​

Solutions:

Interactive Visualization

Analysis

def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
def dfs(row, col):
nonlocal isSubIsland
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(row, col):
return
visited[row][col] = 1
if grid1[row][col] == 0:
isSubIsland = False
dfs(row + 1, col)
dfs(row, col + 1)
dfs(row - 1, col)
dfs(row, col - 1)
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda i, j: visited[i][j]
isIsland = lambda i, j: grid2[i][j] == 1
sub_islands_count = 0
 
m, n = len(grid2), len(grid2[0])
visited = [[0] * n for _ in range(m)]
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
isSubIsland = True
dfs(row, col)
sub_islands_count += isSubIsland
return sub_islands_count

827. Making A Large Island

Hard1 solutionanalysis

827. Making A Large Island​

Solutions:

Interactive Visualization

Analysis

def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if not isValidCell(row, col):
return
if not isIsland(row, col) or isVisited(row, col):
return
visited[row][col] = island_id
island_size[island_id] += 1
for r, c in directions:
dfs(row + r, col + c)
 
def getUniqueNeighborsSum(row, col):
ids = set()
for r, c in directions:
if isValidCell(row + r, col + c):
ids.add(visited[row + r][col + c])
return sum(island_size[i] for i in ids)
 
m, n = len(grid), len(grid[0])
visited = [[0] * n for _ in range(m)]
island_size = collections.Counter()
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
largest_island = 0
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda row, col: visited[row][col] > 0
isIsland = lambda row, col: grid[row][col] == 1
island_id = largest_island = 0
 
for row in range(m):
for col in range(n):
if isIsland(row, col) and not isVisited(row, col):
island_id += 1
dfs(row, col)
 
for row in range(m):
for col in range(n):
if not isIsland(row, col):
largest_island = max(
largest_island, getUniqueNeighborsSum(row, col) + 1
)
 
return largest_island or m * n

Surrounded Regions​

130. Surrounded Regions

Medium1 solutionanalysis

130. Surrounded Regions​

Solutions:

Interactive Visualization

Analysis

def solve(self, board: List[List[str]]) -> None:
def dfs(row, col):
if not isValidCell(row, col) or not isRegion(row, col):
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])
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isRegion = lambda row, col: board[row][col] == "O"
 
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):
match board[row][col]:
case "B":
board[row][col] = "O"
case "O":
board[row][col] = "X"

417. Pacific Atlantic Water Flow

Medium1 solutionanalysis

417. Pacific Atlantic Water Flow​

Solutions:

Interactive Visualization

Analysis

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
def dfs(row, col, prev=0):
if not isValidCell(row, col):
return
if prev > heights[row][col] or isVisited(row, col):
return
visited[row][col] = current_visit
 
reachability[row][col] += current_visit
 
dfs(row + 1, col, heights[row][col])
dfs(row, col + 1, heights[row][col])
dfs(row - 1, col, heights[row][col])
dfs(row, col - 1, heights[row][col])
 
m, n = len(heights), len(heights[0])
reachability = [[0] * n for _ in range(m)]
visited = [[0] * n for _ in range(m)]
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isVisited = lambda row, col: visited[row][col] == current_visit
 
current_visit = 2
for row in range(m):
dfs(row, 0)
for col in range(n):
dfs(0, col)
 
current_visit = 3
for row in range(m):
dfs(row, n - 1)
for col in range(n):
current_visit = 3
dfs(m - 1, col)
 
results = []
for row in range(m):
for col in range(n):
if reachability[row][col] == 5:
results.append([row, col])
return results

1020. Number of Enclaves

Medium1 solutionanalysis

1020. Number of Enclaves​

Solutions:

Interactive Visualization

Analysis

def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if not isValidCell(row, col):
return
if not isLand(row, col) or isVisited(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
 
isValidCell = lambda row, col: (0 <= row < m) and (0 <= col < n)
isLand = lambda row, col: grid[row][col] == 1
isVisited = lambda row, col: visited[row][col]
 
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 isLand(row, col) and not isVisited(row, col):
count += 1
return count