Grid Traversal Fundamentals
Most matrix problems involve: (1) BFS from one or multiple source cells, (2) DFS to explore connected components, (3) dynamic programming over cells in order, or (4) binary search combined with a feasibility check on the matrix. The four-directional neighbors are standard: dirs = [(0,1),(0,-1),(1,0),(-1,0)]. For diagonal problems, add (1,1),(1,-1),(-1,1),(-1,-1).
Number of Islands (LC 200) — DFS / BFS Component Count
def numIslands(grid):
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
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
Rotting Oranges (LC 994) — Multi-Source BFS
BFS from all rotten oranges simultaneously. Each BFS step = 1 minute. Count the number of steps until no fresh orange remains (or return -1 if unreachable).
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: queue.append((r, c, 0))
elif grid[r][c] == 1: fresh += 1
if fresh == 0: return 0
minutes = 0
while queue:
r, c, t = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
minutes = t + 1
queue.append((nr, nc, t+1))
return minutes if fresh == 0 else -1
Walls and Gates (LC 286) — Multi-Source BFS for Distance
Fill each empty cell with its distance to the nearest gate. BFS from all gates simultaneously. Each cell is processed once — O(mn).
def wallsAndGates(rooms):
rows, cols = len(rooms), len(rooms[0])
INF = 2147483647
queue = deque([(r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0])
dist = 0
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
Unique Paths (LC 62) — DP on Grid
def uniquePaths(m, n):
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
for c in range(1, n):
dp[r][c] = dp[r-1][c] + dp[r][c-1]
return dp[m-1][n-1]
Optimized: use a 1D array, updating left-to-right. dp[c] = dp[c] + dp[c-1].
Minimum Path Sum (LC 64) and Maximal Square (LC 221)
# Minimum path sum: DP, dp[r][c] = min cost to reach (r,c)
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = grid[0][:]
for c in range(1, n): dp[c] += dp[c-1]
for r in range(1, m):
dp[0] += grid[r][0]
for c in range(1, n):
dp[c] = grid[r][c] + min(dp[c], dp[c-1])
return dp[-1]
# Maximal square of 1s: dp[r][c] = side length of largest square ending at (r,c)
def maximalSquare(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0]*n for _ in range(m)]
ans = 0
for r in range(m):
for c in range(n):
if matrix[r][c] == '1':
dp[r][c] = 1 + min(
dp[r-1][c] if r > 0 else 0,
dp[r][c-1] if c > 0 else 0,
dp[r-1][c-1] if r > 0 and c > 0 else 0
)
ans = max(ans, dp[r][c])
return ans * ans
Binary Search on Matrix (LC 74, 240)
# LC 74: sorted matrix (rows and cols sorted, row i+1 starts after row i ends)
# Treat as 1D sorted array
def searchMatrix(matrix, target):
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // n][mid % n]
if val == target: return True
elif val < target: lo = mid + 1
else: hi = mid - 1
return False
# LC 240: each row and column sorted independently
# Start top-right: if too big, go left; if too small, go down
def searchMatrixII(matrix, target):
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
Pattern Recognition
- Count/find connected components: DFS or BFS, mark visited in-place
- Shortest distance from multiple sources: multi-source BFS
- Count paths / min cost: DP, process cells in row-major order
- Largest rectangle/square of 1s: DP (maximal square) or stack (LC 84 histogram)
- Search in sorted matrix: binary search (LC 74) or eliminate-corner (LC 240)
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When do you use BFS vs DFS for matrix traversal problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use BFS when: you need the shortest path (minimum steps) from a source to a destination — BFS processes cells in order of distance, so the first time you reach a target cell, it is via the shortest path. Multi-source BFS (start BFS from all sources simultaneously) finds the minimum distance from any source to every cell in O(mn). Use DFS when: you need to explore all connected cells (count islands, flood fill, find all cells in a component) and shortest path does not matter. DFS uses less memory (O(depth) stack vs O(width) queue), but can hit Python recursion limits on large grids — use iterative DFS with an explicit stack or increase sys.setrecursionlimit. For BFS distance problems: store (row, col, distance) in the queue, or use level-by-level BFS. For DFS component problems: mark cells as visited in-place (modify the grid) to avoid a separate visited array.”}},{“@type”:”Question”,”name”:”How does multi-source BFS work for problems like Rotting Oranges (LC 994)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Multi-source BFS starts BFS from multiple source cells simultaneously rather than a single source. Initialize the queue with all source cells at time=0. BFS proceeds in waves — all cells at distance 1 from any source are processed before any cell at distance 2. This correctly computes the minimum distance from the nearest source to every reachable cell. Algorithm for Rotting Oranges: add all initially rotten oranges to the queue with time=0. BFS: for each rotten cell, rot its fresh neighbors and add them to the queue with time+1. Track fresh orange count — if any fresh orange remains after BFS, return -1. Return the maximum time seen. Multi-source BFS is equivalent to single-source BFS on a virtual super-source connected to all actual sources — conceptually clean and efficient at O(mn).”}},{“@type”:”Question”,”name”:”How does the DP for maximal square (LC 221) work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[r][c] represents the side length of the largest square of 1s whose bottom-right corner is at (r, c). Recurrence: if matrix[r][c] == 1: dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]). Intuition: the largest square ending at (r,c) is limited by the smallest of the three adjacent squares (above, left, diagonal). If any of those three is k, you can extend by 1 in all directions from them, but the bottleneck is the smallest. If matrix[r][c] == 0: dp[r][c] = 0 (no square here). Answer: max(dp[r][c])^2. Time O(mn), space O(mn) or O(n) with rolling array. This recurrence only works for squares — for rectangles, use the largest rectangle in histogram approach (LC 84) applied row by row.”}},{“@type”:”Question”,”name”:”How do you solve Search a 2D Matrix (LC 74) in O(log(m*n)) time?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 74: a matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. This means the entire matrix is sorted as a 1D array when read left-to-right, top-to-bottom. Treat it as a 1D binary search: lo=0, hi=m*n-1. At each step, mid = (lo+hi)//2. To convert mid to (row, col): row = mid // n, col = mid % n. Compare matrix[row][col] to target and adjust lo/hi. Time O(log(mn)). LC 240: each row and each column is sorted independently (not globally sorted). Approach: start at the top-right corner. If the current value is too large, move left (eliminate the current column). If too small, move down (eliminate the current row). Each step eliminates a row or column. Time O(m+n).”}},{“@type”:”Question”,”name”:”How do you handle the grid boundary check efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In-bounds check: the standard check is 0 <= r < rows and 0 <= c < cols. Place this check before accessing grid[r][c]. Pattern with direction array: for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc = r+dr, c+dc; if 0 <= nr < rows and 0 <= nc < cols: process grid[nr][nc]. Sentinel approach: add a border of sentinel values around the grid (e.g., a layer of 0s). This eliminates the bounds check inside the loop at the cost of O(m+n) extra space and O(m+n) initialization. For Python, the explicit bounds check is idiomatic. For visited tracking: modify the grid in-place (grid[r][c] = VISITED_MARKER) instead of a separate boolean array — O(1) space. Restore the grid after DFS if the problem requires the original values (restore on backtrack).”}}]}
Google coding interviews frequently test matrix traversal patterns. See common questions for Google interview: matrix traversal and grid problems.
Meta coding interviews cover matrix traversal and BFS/DFS grid problems. Review patterns for Meta interview: matrix and grid coding problems.
Amazon coding interviews test BFS and matrix grid problems. See patterns for Amazon interview: matrix traversal and BFS problems.