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 step
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the standard template for 2D grid BFS/DFS in coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Define DIRS = [(0,1),(0,-1),(1,0),(-1,0)] for 4-directional movement (add diagonals if needed). Before adding a neighbor to the queue, validate: in-bounds (0 <= nr < rows and 0 <= nc < cols) and unvisited and valid (not a wall/water). Mark visited before pushing to queue (not when popping) to avoid duplicate entries. For DFS, mark the cell as visited (modify grid in-place as '0' or use a separate visited array) before recursing. Most connected-component problems on grids (LC 200, 130, 695) follow this template.”}},{“@type”:”Question”,”name”:”What is multi-source BFS and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Multi-source BFS starts from multiple source nodes simultaneously by adding all sources to the BFS queue before the first iteration. This finds the shortest distance from each cell to the nearest source in a single BFS pass, instead of running BFS from each source separately. LC 542 (01 Matrix): add all 0-cells as sources with distance 0, BFS outward. LC 994 (Rotting Oranges): add all rotten oranges as sources, BFS spreading. Time complexity: O(rows * cols) – same as single-source BFS, but processes all sources in one pass.”}},{“@type”:”Question”,”name”:”How do you rotate a matrix 90 degrees clockwise in-place?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two-step process: (1) Transpose the matrix: swap matrix[i][j] with matrix[j][i] for all i < j. (2) Reverse each row. The combination achieves a 90-degree clockwise rotation. For 90-degree counter-clockwise: reverse each row first, then transpose (or transpose first, then reverse each column). For 180-degree rotation: reverse each row, then reverse the matrix (or apply 90-degree rotation twice). The in-place approach uses O(1) extra space and O(n^2) time. This is LC 48.”}},{“@type”:”Question”,”name”:”How do you search a 2D matrix where rows and columns are both sorted?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For LC 240 (rows sorted left-to-right, columns sorted top-to-bottom, but first element of row not necessarily greater than last of previous row): start at the top-right corner. If matrix[r][c] == target: found. If matrix[r][c] > target: move left (c -= 1) – eliminates this column. If matrix[r][c] < target: move down (r += 1) – eliminates this row. Each step eliminates one row or column, giving O(m + n) time. For LC 74 (each row sorted, first of row > last of previous row): treat as flattened 1D sorted array and binary search with index mapping: val = matrix[mid // cols][mid % cols].”}},{“@type”:”Question”,”name”:”How do you traverse a matrix in spiral order?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use four boundary pointers: top, bottom, left, right. Traverse: left to right along top row (then top++), top to bottom along right column (then right–), right to left along bottom row if top <= bottom (then bottom–), bottom to top along left column if left <= right (then left++). Continue while top <= bottom and left <= right. Handle the boundary checks for the reverse passes to avoid duplicating the last row/column in non-square matrices. This is LC 54 (Spiral Matrix), O(m*n) time and O(1) extra space.”}}]}
Meta 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.