DFS

Depth-first search on a grid: each cell is a vertex with edges to its 4 neighbours, and from any unvisited cell DFS floods as far as it can before backtracking. See Grids as Graphs for the neighbour function, the visited choices, and why the recursive version dies on a large grid.

Connected Components

A maximal set of cells all reachable from each other. The two-loop shape - outer scan finds fresh land, inner traversal sinks the whole island - is flood fill.

200. Number of Islands

Medium·

200Number of Islands

2 Approaches · 2 patterns

DFS - Recursive

O(m*n) timeO(2mn) aux

DSU: Cell-Index Mapping↗ DSU on Grid

O(m*n*α(m*n)) timeO(3mn) aux

FIG. 200 NUMBER OF ISLANDS● INTERACTIVE

visualization loads as you reach it

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

Medium·

419Battleships in a Board

DFS - Recursive

O(m*n) timeO(2mn) aux

FIG. 419 BATTLESHIPS IN A BOARD● INTERACTIVE

visualization loads as you reach it

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

Medium·

694Number of Distinct Islands

DFS - Recursive

O(m*n) timeO(6*m*n) aux

FIG. 694 NUMBER OF DISTINCT ISLANDS● INTERACTIVE

visualization loads as you reach it

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

Easy·

733Flood Fill

DFS - Recursive

O(m*n) timeO(2mn) aux

FIG. 733 FLOOD FILL● INTERACTIVE

visualization loads as you reach it

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

Medium·

1034Coloring A Border

DFS - Two Phase

O(m*n) timeO(3mn) aux

FIG. 1034 COLORING A BORDER● INTERACTIVE

visualization loads as you reach it

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

Easy·

463Island Perimeter

DFS - Recursive

O(2mn) timeO(2mn) aux

FIG. 463 ISLAND PERIMETER● INTERACTIVE

visualization loads as you reach it

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

Medium·

695Max Area of Island

2 Approaches · 2 patterns

DFS - Recursive

O(m*n) timeO(2mn) aux

DSU: getSize After Each Union↗ DSU on Grid

O(m*n*α(m*n)) timeO(3mn) aux

FIG. 695 MAX AREA OF ISLAND● INTERACTIVE

visualization loads as you reach it

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

Medium·

3619Count Islands With Total Value Divisible by K

DFS - Recursive

O(m*n) timeO(2mn) aux

FIG. 3619 COUNT ISLANDS DIVISIBLE● INTERACTIVE

visualization loads as you reach it

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

Medium·

1254Number of Closed Islands

DFS - Recursive

O(m*n) timeO(2mn) aux

FIG. 1254 NUMBER OF CLOSED ISLANDS● INTERACTIVE

visualization loads as you reach it

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

Medium·

1905Count Sub Islands

DFS - Recursive

O(m*n) timeO(2mn) aux

FIG. 1905 COUNT SUB ISLANDS● INTERACTIVE

visualization loads as you reach it

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

Hard·

827Making A Large Island

DFS + Island Labeling

O(2mn) timeO(3mn) aux

FIG. 827 MAKING A LARGE ISLAND● INTERACTIVE

visualization loads as you reach it

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

Regions defined by what they cannot reach. Detecting "enclosed" directly is awkward; flooding inward from the border to mark what escapes, then flipping the rest, is one traversal - the border-seeded inversion.

130. Surrounded Regions

Medium·

130Surrounded Regions

DFS - Recursive

O(2mn) timeO(mn) aux

FIG. 130 SURROUNDED REGIONS● INTERACTIVE

visualization loads as you reach it

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

Medium·

417Pacific Atlantic Water Flow

DFS - Recursive

O(3*m*n) timeO(3*m*n) aux

FIG. 417 PACIFIC ATLANTIC WATER FLOW● INTERACTIVE

visualization loads as you reach it

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

Medium·

1020Number of Enclaves

DFS - Recursive

O(2mn) timeO(2mn) aux

FIG. 1020 NUMBER OF ENCLAVES● INTERACTIVE

visualization loads as you reach it

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

---