Matrix Problems: Traversal, Search, and Manipulation Patterns

Matrix problems are a staple of coding interviews because they combine spatial reasoning with algorithmic thinking. You need to navigate a 2D grid, track which cells you've visited, handle boundaries without going out of bounds, and apply patterns like BFS, DFS, and binary search in a spatial context.

The good news: there's a finite set of patterns, and once you've seen each one, new matrix problems feel like variations rather than novelties.

The Basics: Navigating a Grid

Before diving into patterns, make sure these fundamentals are second nature.

Dimensions:

rows = len(matrix)
cols = len(matrix[0])

Four-directional movement:

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up

Eight-directional movement (for problems that include diagonals):

directions = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)]

Bounds checking:

def is_valid(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

These three things — dimensions, directions, bounds checking — show up in every single matrix problem. Having them as automatic patterns saves you time and prevents off-by-one errors.

Pattern 1: DFS on Grids

Depth-first search on a grid is used whenever you need to explore connected regions — groups of cells that share some property and are adjacent to each other.

Problem: Number of Islands

Given a grid of '1's (land) and '0's (water), count the number of islands. An island is a group of connected '1's (horizontally or vertically).

def num_islands(grid):
    if not grid:
        return 0

rows, cols = len(grid), len(grid[0])
    count = 0

def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited by sinking the island
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

return count

For every unvisited land cell, start a DFS that marks all connected land as visited (by changing '1' to '0'). Each DFS call finds one complete island.

O(rows * cols) time and space.

If you can't modify the input, use a separate visited set:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

def dfs(r, c):
        if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        visited.add((r, c))
        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' and (r, c) not in visited:
                count += 1
                dfs(r, c)

return count

Problem: Max Area of Island

Same as number of islands, but return the size of the largest island.

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])

def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)

max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

return max_area

The DFS returns the count of cells it visited. Clean and elegant.

Problem: Surrounded Regions

Capture all 'O' regions that are completely surrounded by 'X'. An 'O' on the border (or connected to a border 'O') cannot be captured.

The trick: instead of finding surrounded regions, find un-surrounded ones. DFS from every 'O' on the border and mark them as safe. Everything else gets captured.

def solve(board):
    if not board:
        return

rows, cols = len(board), len(board[0])

def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'S'  # safe
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            dfs(r + dr, c + dc)

# mark border-connected O's as safe
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

# capture surrounded O's, restore safe ones
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'S':
                board[r][c] = 'O'

Pattern 2: BFS on Grids

Use BFS when you need the shortest path or when the problem involves expanding outward level by level (like a wave or a spreading fire).

Problem: Rotting Oranges

Every minute, fresh oranges adjacent to rotten ones become rotten. Return the minimum number of minutes until all oranges are rotten, or -1 if impossible.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

# initialize: all rotten oranges in queue, count fresh
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

if fresh == 0:
        return 0

minutes = 0
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):  # process one level
            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 grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

return minutes if fresh == 0 else -1

Multi-source BFS: start from all rotten oranges simultaneously. Each BFS level represents one minute. This is a classic pattern for "spreading" problems.

Problem: Shortest Path in Binary Matrix

Find the shortest path from top-left to bottom-right in a binary grid, moving in 8 directions.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] != 0 or grid[n-1][n-1] != 0:
        return -1

queue = deque([(0, 0, 1)])  # row, col, distance
    grid[0][0] = 1  # mark visited

directions = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]

while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == n - 1:
            return dist
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1
                queue.append((nr, nc, dist + 1))

return -1

BFS guarantees the first time you reach the destination is the shortest path. This is true because all "edges" in the grid have equal weight (1 step).

Problem: Walls and Gates (01 Matrix variant)

Given a grid with 0 (gate) and INF (empty room), fill each empty room with the distance to its nearest gate.

from collections import deque

def walls_and_gates(rooms):
    if not rooms:
        return

rows, cols = len(rooms), len(rooms[0])
    INF = 2147483647
    queue = deque()

# start BFS from all gates
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))

while 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))

Another multi-source BFS. Start from all gates and expand outward. The first time you reach an empty room is the shortest distance from any gate.

Pattern 3: Spiral Traversal

Problem: Spiral Matrix

Given an m x n matrix, return all elements in spiral order.

def spiral_order(matrix):
    result = []
    if not matrix:
        return result

top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

while top <= bottom and left <= right:
        # traverse right
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1

# traverse down
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1

# traverse left
        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1

# traverse up
        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1

return result

Four boundaries: top, bottom, left, right. Move in the four directions in order (right, down, left, up), shrinking the boundary after each pass. The if top <= bottom and if left <= right checks prevent revisiting rows/columns in non-square matrices.

Problem: Spiral Matrix II

Fill an n x n matrix with numbers 1 to n^2 in spiral order. Same boundary approach, but write instead of read:

def generate_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    num = 1
    top, bottom, left, right = 0, n - 1, 0, n - 1

while top <= bottom and left <= right:
        for c in range(left, right + 1):
            matrix[top][c] = num
            num += 1
        top += 1

for r in range(top, bottom + 1):
            matrix[r][right] = num
            num += 1
        right -= 1

if top <= bottom:
            for c in range(right, left - 1, -1):
                matrix[bottom][c] = num
                num += 1
            bottom -= 1

if left <= right:
            for r in range(bottom, top - 1, -1):
                matrix[r][left] = num
                num += 1
            left += 1

return matrix

Pattern 4: Binary Search in a Sorted Matrix

Problem: Search a 2D Matrix

Each row is sorted, and the first element of each row is greater than the last element of the previous row. Search for a target.

Treat the matrix as a flattened sorted array:

def search_matrix(matrix, target):
    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 < target:
            lo = mid + 1
        else:
            hi = mid - 1

return False

The key conversion: index mid in the flattened array corresponds to row mid // cols and column mid % cols. O(log(m * n)).

Problem: Search a 2D Matrix II

Each row is sorted left to right, each column is sorted top to bottom, but the first element of a row is NOT necessarily greater than the last element of the previous row.

Start from the top-right corner:

def search_matrix_ii(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    r, c = 0, cols - 1

while r < rows and c >= 0:
        if matrix[r][c] == target:
            return True
        elif matrix[r][c] > target:
            c -= 1  # eliminate this column
        else:
            r += 1  # eliminate this row

return False

From the top-right corner, going left gives smaller values, going down gives larger values. Each step eliminates either a row or a column. O(m + n).

This is one of the most elegant algorithms in all of matrix problems. The top-right (or bottom-left) corner is special because it gives you a binary decision at each step.

Pattern 5: Matrix Rotation and Transposition

Problem: Rotate Image (90 degrees clockwise)

Rotate an n x n matrix in place.

def rotate(matrix):
    n = len(matrix)

# step 1: transpose (swap rows and columns)
    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()

Transpose + reverse rows = 90-degree clockwise rotation. For counter-clockwise, transpose + reverse columns (or reverse rows first, then transpose).

Why does this work? Transposing flips the matrix along the main diagonal. Reversing each row then flips it horizontally. The composition of these two transformations is a 90-degree rotation.

Problem: Rotate Image (90 degrees counter-clockwise)

def rotate_ccw(matrix):
    n = len(matrix)

# transpose
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# reverse each column
    for j in range(n):
        top, bottom = 0, n - 1
        while top < bottom:
            matrix[top][j], matrix[bottom][j] = matrix[bottom][j], matrix[top][j]
            top += 1
            bottom -= 1

Pattern 6: Diagonal Traversal

Problem: Diagonal Traverse

Given an m x n matrix, return all elements in diagonal order.

def find_diagonal_order(matrix):
    if not matrix:
        return []

rows, cols = len(matrix), len(matrix[0])
    result = []
    r, c = 0, 0
    going_up = True

for _ in range(rows * cols):
        result.append(matrix[r][c])

if going_up:
            if c == cols - 1:       # hit right wall
                r += 1
                going_up = False
            elif r == 0:            # hit top wall
                c += 1
                going_up = False
            else:
                r -= 1
                c += 1
        else:
            if r == rows - 1:       # hit bottom wall
                c += 1
                going_up = True
            elif c == 0:            # hit left wall
                r += 1
                going_up = True
            else:
                r += 1
                c -= 1

return result

The trick is handling the direction changes when you hit the boundaries. Going up means r decreases and c increases. Going down means r increases and c decreases. When you hit a boundary, change direction and adjust position.

Common Mistakes

Off-by-one errors in boundary checks. r < rows not r <= rows. c >= 0 not c > 0. Get these wrong and you'll access invalid indices. Always use 0 <= r < rows and 0 <= c < cols. Forgetting to mark cells as visited. In DFS/BFS on grids, if you don't mark cells as visited, you'll revisit them infinitely (or until you hit the recursion limit). Mark before recursing, not after. Using DFS when BFS is required. DFS does not guarantee shortest path. If the problem asks for minimum steps or shortest distance, use BFS. Stack overflow with DFS on large grids. Python's default recursion limit is 1000. For large grids, either increase it with sys.setrecursionlimit() or convert to iterative DFS with an explicit stack. Modifying the matrix when you shouldn't. Some problems expect the original matrix to be preserved. Use a separate visited set instead of modifying the grid in place. Wrong direction array. For 4-directional movement, you need exactly 4 directions. For 8-directional, exactly 8. Accidentally including (0,0) means "staying in place," which creates infinite loops.

Practice Problems

DFS: Number of Islands, Max Area of Island, Surrounded Regions, Pacific Atlantic Water Flow, Number of Distinct Islands BFS: Rotting Oranges, Shortest Path in Binary Matrix, 01 Matrix, Walls and Gates, Word Ladder (not matrix-based but same BFS pattern) Spiral: Spiral Matrix, Spiral Matrix II Binary Search: Search a 2D Matrix, Search a 2D Matrix II, Kth Smallest Element in a Sorted Matrix Rotation/Traversal: Rotate Image, Diagonal Traverse, Reshape the Matrix, Set Matrix Zeroes

Practice these on CodeUp — matrix problems are visual, so draw the grid on paper and trace through your code. That habit alone will eliminate most of the bugs.