Matrix Traversal Interview Patterns

By /
⏱ 7 min read

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)

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.

Scroll to Top