2D Grid BFS and DFS Fundamentals
from collections import deque
DIRS = [(0,1),(0,-1),(1,0),(-1,0)] # right, left, down, up
def bfs_grid(grid, start_r, start_c):
rows, cols = len(grid), len(grid[0])
visited = [[False]*cols for _ in range(rows)]
queue = deque([(start_r, start_c)])
visited[start_r][start_c] = True
while queue:
r, c = queue.popleft()
# process (r, c)
for dr, dc in DIRS:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc int:
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r = rows or c = cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited in-place
for dr, dc in DIRS:
dfs(r+dr, c+dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countMulti-Source BFS and Distance Transforms
# 01 Matrix (LC 542): distance from each cell to nearest 0
def update_matrix(mat: list[list[int]]) -> list[list[int]]:
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
# Initialize: all 0-cells have distance 0, add to queue
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
# BFS outward from all sources simultaneously
while queue:
r, c = queue.popleft()
for dr, dc in DIRS:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols:
if dist[r][c] + 1 < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
# Key insight: starting BFS from ALL 0-cells at once gives correct distancesMatrix Rotation and Transformation
# Rotate matrix 90 degrees clockwise in-place (LC 48)
def rotate(matrix: list[list[int]]) -> None:
n = len(matrix)
# Step 1: transpose (swap matrix[i][j] and matrix[j][i])
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: reverse each row
for row in matrix:
row.reverse()
# 90 CCW: reverse each row, then transpose
# Spiral order traversal (LC 54)
def spiral_order(matrix: list[list[int]]) -> list[int]:
result = []
top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
while top <= bottom and left <= right:
for c in range(left, right+1): result.append(matrix[top][c])
top += 1
for r in range(top, bottom+1): result.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left-1, -1): result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top-1, -1): result.append(matrix[r][left])
left += 1
return resultBinary Search on Sorted Matrix
# Search in 2D sorted matrix (LC 240): each row sorted, first element of row > last of prev row
def search_matrix_i(matrix, target) -> bool:
# Treat as flattened sorted array
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // cols][mid % cols]
if val == target: return True
elif val bool:
# Start from top-right corner: go left if too big, down if too small
r, c = 0, len(matrix[0]) - 1
while r = 0:
if matrix[r][c] == target: return True
elif matrix[r][c] > target: c -= 1
else: r += 1
return False
# O(m + n): eliminates one row or column per stepMeta coding interviews heavily test 2D grid and matrix problems. See patterns at Meta interview: matrix and 2D grid problems.
Apple coding interviews test matrix manipulation and 2D search. Review patterns for Apple interview: matrix manipulation and search.
Databricks interviews include matrix and multi-dimensional data processing. See patterns for Databricks interview: matrix and multi-dimensional data problems.