Skip to main content

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·
FIG. 200 NUMBER OF ISLANDS● INTERACTIVE
visualization loads as you reach it
Time
O(m*n)
  • m and n are the grid's row and column counts. The nested scan visits each of the m*n cells once, and dfs visits each land cell at most once thanks to the visited guard.
Space
O(m*n)
  • visited is an m*n grid. The recursion call stack can also grow to m*n in the worst case (one giant island snaking through every cell).
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·
FIG. 419 BATTLESHIPS IN A BOARD● INTERACTIVE
visualization loads as you reach it
Time
O(m*n)
  • The for row in range(m): for col in range(n) double loop visits every cell once; dfs marks each X cell in visited exactly once and returns immediately on already-visited or non-X cells, so total work is O(m*n), where m is the number of rows and n is the number of columns.
Space
O(m*n)
  • visited is a full m x n grid: O(m*n).
  • The recursion stack adds at most O(m*n) more in the worst case (a single battleship snaking through every cell), which does not change the overall order.
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·
FIG. 694 NUMBER OF DISTINCT ISLANDS● INTERACTIVE
visualization loads as you reach it
Time
O(m×n)
  • dfs visits each of the m×n cells at most once, guarded by visited.
Space
O(m×n)
  • visited is an m×n array, and across all islands the total length of every path recorded into island_signature is bounded by m×n cells.
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·
FIG. 733 FLOOD FILL● INTERACTIVE
visualization loads as you reach it
Time
O(m*n)
  • m is the number of rows, n is the number of columns - dfs visits every cell at most once, guarded by the visited check.
Space
O(m*n)
  • visited allocates one entry per cell, O(m*n).
  • The dfs recursion stack can grow to O(m*n) frames in the worst case, when the whole grid is one connected region.
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·
FIG. 1034 COLORING A BORDER● INTERACTIVE
visualization loads as you reach it
Time
O(m×n)
  • dfs visits each of the grid's m × n cells at most once, since visited[r][c] gates re-entry.
Space
O(m×n)
  • visited and borders are each a full m × n matrix.
  • The dfs recursion stack can also grow to O(m×n) in the worst case, but stays the same order as the two matrices.
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·
FIG. 463 ISLAND PERIMETER● INTERACTIVE
visualization loads as you reach it
Time
O(2mn)
  • m is the number of rows, n is the number of columns.
  • The outer scan (for row in range(m): for col in range(n)) looking for the first unvisited land cell is one O(mn) pass in the worst case (the island sits at the far end of row-major order).
  • The dfs call visits every land cell exactly once (visited[row][col] guards re-entry), a second O(mn) pass in the worst case (grid is all land).
Space
O(2mn)
  • visited is an m x n matrix - O(mn).
  • The recursive dfs call stack can go as deep as the number of land cells in a snake-shaped island - another O(mn) in the worst case.
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·
FIG. 695 MAX AREA OF ISLAND● INTERACTIVE
visualization loads as you reach it
Time
O(m×n)
  • m and n are the grid's row and column counts. The outer double loop visits each cell once, and dfs visits each land cell at most once thanks to the visited check.
Space
O(m×n)
  • visited is an m×n matrix.
  • The recursion stack can also grow to m×n frames in the worst case (one fully connected island) - the same order as visited.
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·
FIG. 3619 COUNT ISLANDS DIVISIBLE● INTERACTIVE
visualization loads as you reach it
Time
O(m * n)
  • m, n = len(grid), len(grid[0]). The for row/for col scan visits every cell once, and dfs only recurses into a cell if it is unvisited land, so each of the m * n cells is processed by dfs exactly once overall.
Space
O(m * n)
  • visited is an m by n matrix - O(m * n).
  • The dfs recursion call stack can grow to hold every cell of a single island, up to m * n frames in the worst case (one connected island spanning the whole grid).
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·
FIG. 1254 NUMBER OF CLOSED ISLANDS● INTERACTIVE
visualization loads as you reach it
Time
O(m×n)
  • The double loop over row/col visits each of the m × n cells, and dfs marks each land cell visited at most once before returning.
Space
O(m×n)
  • visited is an m × n grid.
  • The dfs recursion stack can grow to O(m×n) in the worst case (a single island spanning the whole grid).
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·
FIG. 1905 COUNT SUB ISLANDS● INTERACTIVE
visualization loads as you reach it
Time
O(m * n)
  • The outer for row / for col loop scans all m * n cells; dfs visits any given cell at most once thanks to the visited guard, so total work across all dfs calls is bounded by m * n.
Space
O(2 * m * n)
  • visited is an m by n grid, O(m * n).
  • dfs recurses into all 4 directions, so on a snake-shaped island the call stack can hold up to m * n frames - another O(m * n) term of the same order.
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·
FIG. 827 MAKING A LARGE ISLAND● INTERACTIVE
visualization loads as you reach it
Time
O(2mn)
  • The first nested loop scans all m×n cells; dfs labels every land cell exactly once (guarded by visited) - mn.
  • The second nested loop scans all m×n cells again, checking at most 4 neighbors per water cell in O(1) - mn.
  • Two full grid passes, each O(mn) - 2mn.
Space
O(mn)
  • visited is an m×n grid.
  • island_size holds at most one entry per island, bounded by mn.
  • The dfs recursion stack can go as deep as the largest island, up to mn in the worst case (one giant island).
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·
FIG. 130 SURROUNDED REGIONS● INTERACTIVE
visualization loads as you reach it
Time
O(2mn)
  • m and n are the board's rows and columns. The border-triggered dfs calls mark each reachable 'O' cell as 'B' at most once, so the flood is bounded by O(mn). The final double loop over every cell is another O(mn) pass - two same-order passes collapse to 2mn.
Space
O(mn)
  • In the worst case (a snake-shaped safe region), the recursion depth of dfs grows to the total number of cells, mn.
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·
FIG. 417 PACIFIC ATLANTIC WATER FLOW● INTERACTIVE
visualization loads as you reach it
Time
O(3·m×n)
  • The pacific DFS is started from every cell on the top row and left column (m + n starts), but the visited[row][col] guard means no cell is ever explored twice across all of those starts - total work for the whole pacific pass is O(m×n).
  • The atlantic DFS is symmetric (started from the bottom row and right column) and is also bounded to O(m×n) total work for the same reason.
  • The final double loop over row/col to collect cells reachable from both oceans is one more O(m×n) pass - m×n + m×n + m×n.
Space
O(4·m×n)
  • pacific and atlantic are each m×n matrices - two terms of m×n.
  • The dfs recursion can, in the worst case (e.g. strictly increasing heights), chain through every cell before backtracking, so the call stack depth is up to O(m×n).
  • results can hold up to every cell in the grid, another O(m×n) - m×n + m×n + m×n + m×n.
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·
FIG. 1020 NUMBER OF ENCLAVES● INTERACTIVE
visualization loads as you reach it
Time
O(m×n)
  • dfs visits and marks each of the m×n cells at most once.
Space
O(m×n)
  • visited is an m×n array; the recursion stack can grow to O(m×n) in the worst case (e.g. one long snaking path of land).
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