Matrix Traversal Patterns: Spiral, Diagonal, Rotation

Matrix problems are a staple of coding interviews. They test your ability to manipulate indices carefully, think about boundary conditions, and translate spatial patterns into code. This post covers every major traversal pattern you will encounter, plus common transformation operations.

---

1. Row-by-Row and Column-by-Column

The simplest traversals — good for warm-up and understanding the coordinate system.

def row_traversal(matrix):
    """Traverse matrix row by row (left to right)."""
    result = []
    for row in matrix:
        for val in row:
            result.append(val)
    return result


def column_traversal(matrix):
    """Traverse matrix column by column (top to bottom)."""
    if not matrix:
        return []
    rows, cols = len(matrix), len(matrix[0])
    result = []
    for c in range(cols):
        for r in range(rows):
            result.append(matrix[r][c])
    return result


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
print("Row:", row_traversal(matrix))     # [1,2,3,4,5,6,7,8,9]
print("Column:", column_traversal(matrix))  # [1,4,7,2,5,8,3,6,9]

---

2. Spiral Order Traversal

Problem: traverse the matrix in spiral order — right along the top row, down the right column, left along the bottom row, up the left column, then repeat for the inner layers.

def spiral_order(matrix):
    """
    LeetCode 54: Spiral Matrix.

    Traverse matrix in spiral order.

    Time: O(m * n)
    Space: O(1) extra (excluding output)
    """
    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 along top row
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1

        # Traverse down along right column
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1

        # Traverse left along bottom row (if still valid)
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1

        # Traverse up along left column (if still valid)
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1

    return result


matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12],
]
print(spiral_order(matrix))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Generate Spiral Matrix

def generate_spiral_matrix(n):
    """
    LeetCode 59: Spiral Matrix II.

    Generate an n x n matrix filled with 1 to n^2 in spiral order.
    """
    matrix = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    num = 1

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

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

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

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

    return matrix


for row in generate_spiral_matrix(4):
    print(row)
# [1,  2,  3,  4]
# [12, 13, 14, 5]
# [11, 16, 15, 6]
# [10, 9,  8,  7]

---

3. Diagonal Traversal

Problem: traverse the matrix along diagonals from top-right to bottom-left.

def diagonal_traversal(matrix):
    """
    LeetCode 498: Diagonal Traverse.

    Traverse diagonals in zigzag order (alternating direction).

    Time: O(m * n)
    Space: O(1) extra
    """
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    result = []
    row, col = 0, 0
    going_up = True

    for _ in range(m * n):
        result.append(matrix[row][col])

        if going_up:
            if col == n - 1:
                row += 1
                going_up = False
            elif row == 0:
                col += 1
                going_up = False
            else:
                row -= 1
                col += 1
        else:
            if row == m - 1:
                col += 1
                going_up = True
            elif col == 0:
                row += 1
                going_up = True
            else:
                row += 1
                col -= 1

    return result


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
print(diagonal_traversal(matrix))
# [1, 2, 4, 7, 5, 3, 6, 8, 9] — note the zigzag

Anti-Diagonal Grouping

def anti_diagonal_groups(matrix):
    """
    Group elements by anti-diagonal (top-right to bottom-left).
    Elements on the same anti-diagonal have the same r + c value.
    """
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    diagonals = {}

    for r in range(m):
        for c in range(n):
            key = r + c
            if key not in diagonals:
                diagonals[key] = []
            diagonals[key].append(matrix[r][c])

    return [diagonals[k] for k in sorted(diagonals.keys())]


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
print(anti_diagonal_groups(matrix))
# [[1], [2, 4], [3, 5, 7], [6, 8], [9]]

---

4. Zigzag (Snake) Traversal

def zigzag_traversal(matrix):
    """
    Traverse row by row, alternating direction.
    Even rows: left to right. Odd rows: right to left.
    """
    result = []
    for i, row in enumerate(matrix):
        if i % 2 == 0:
            result.extend(row)
        else:
            result.extend(reversed(row))
    return result


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
print(zigzag_traversal(matrix))
# [1, 2, 3, 6, 5, 4, 7, 8, 9]

---

5. Boundary Traversal

def boundary_traversal(matrix):
    """
    Traverse only the boundary elements of the matrix.

    Time: O(m + n)
    """
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    if m == 1:
        return matrix[0][:]
    if n == 1:
        return [matrix[r][0] for r in range(m)]

    result = []

    # Top row (left to right)
    result.extend(matrix[0])

    # Right column (top+1 to bottom-1)
    for r in range(1, m - 1):
        result.append(matrix[r][n - 1])

    # Bottom row (right to left)
    result.extend(reversed(matrix[m - 1]))

    # Left column (bottom-1 to top+1)
    for r in range(m - 2, 0, -1):
        result.append(matrix[r][0])

    return result


matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12],
    [13, 14, 15, 16],
]
print(boundary_traversal(matrix))
# [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5]

---

6. Matrix Rotation — 90 Degrees Clockwise

Key insight: rotating 90 degrees clockwise = transpose + reverse each row.

def rotate_90_clockwise(matrix):
    """
    LeetCode 48: Rotate Image.

    Rotate n x n matrix 90 degrees clockwise IN PLACE.

    Step 1: Transpose (swap rows and columns)
    Step 2: Reverse each row

    Time: O(n^2), Space: O(1)
    """
    n = len(matrix)

    # Step 1: 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]

    # Step 2: Reverse each row
    for row in matrix:
        row.reverse()


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
rotate_90_clockwise(matrix)
for row in matrix:
    print(row)
# [7, 4, 1]
# [8, 5, 2]
# [9, 6, 3]

90 Degrees Counter-Clockwise

def rotate_90_counter_clockwise(matrix):
    """
    Rotate 90 degrees counter-clockwise = transpose + reverse each column.
    Equivalently: reverse each row, then transpose.
    """
    n = len(matrix)

    # Reverse each row first
    for row in matrix:
        row.reverse()

    # Then 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]

180 Degrees

def rotate_180(matrix):
    """Rotate 180 degrees = reverse each row, then reverse row order."""
    matrix.reverse()
    for row in matrix:
        row.reverse()

---

7. Matrix Transpose

def transpose(matrix):
    """
    LeetCode 867: Transpose Matrix.

    For non-square matrices, creates a new matrix.

    Time: O(m * n)
    """
    m, n = len(matrix), len(matrix[0])
    result = [[0] * m for _ in range(n)]

    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]

    return result


matrix = [
    [1, 2, 3],
    [4, 5, 6],
]
transposed = transpose(matrix)
for row in transposed:
    print(row)
# [1, 4]
# [2, 5]
# [3, 6]

---

8. Set Matrix Zeroes

Problem: if an element is 0, set its entire row and column to 0. Do it in-place.

def set_zeroes(matrix):
    """
    LeetCode 73: Set Matrix Zeroes.

    In-place, O(1) extra space.

    Use first row and first column as markers.
    """
    m, n = len(matrix), len(matrix[0])

    # Check if first row/column should be zeroed
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))

    # Use first row/col as markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # Zero out cells based on markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    # Handle first row
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0

    # Handle first column
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0


matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
]
set_zeroes(matrix)
for row in matrix:
    print(row)
# [1, 0, 1]
# [0, 0, 0]
# [1, 0, 1]

---

9. Search in a 2D Matrix

Sorted Rows and Columns (Staircase Search)

def search_matrix_staircase(matrix, target):
    """
    LeetCode 240: Search a 2D Matrix II.

    Each row is sorted left to right.
    Each column is sorted top to bottom.

    Start from top-right corner and use staircase search.

    Time: O(m + n)
    """
    if not matrix:
        return False

    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start at top-right

    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # too big, move left
        else:
            row += 1  # too small, move down

    return False


matrix = [
    [1,  4,  7,  11, 15],
    [2,  5,  8,  12, 19],
    [3,  6,  9,  16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30],
]
print(search_matrix_staircase(matrix, 5))   # True
print(search_matrix_staircase(matrix, 20))  # False

Fully Sorted Matrix (Binary Search)

def search_matrix_binary(matrix, target):
    """
    LeetCode 74: Search a 2D Matrix.

    First integer of each row > last integer of previous row.
    Treat as a sorted 1D array and binary search.

    Time: O(log(m * n))
    """
    if not matrix:
        return False

    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        row, col = divmod(mid, n)
        val = matrix[row][col]

        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return False


matrix = [
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
print(search_matrix_binary(matrix, 3))   # True
print(search_matrix_binary(matrix, 13))  # False

---

10. Word Search in a Grid

def word_search(board, word):
    """
    LeetCode 79: Word Search.

    Find if word exists in the grid by following adjacent cells
    (horizontally or vertically). Each cell used at most once.

    Time: O(m * n * 4^L) where L = len(word)
    """
    m, n = len(board), len(board[0])

    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= m or c < 0 or c >= n:
            return False
        if board[r][c] != word[idx]:
            return False

        # Mark as visited
        temp = board[r][c]
        board[r][c] = '#'

        # Explore 4 directions
        found = (
            dfs(r + 1, c, idx + 1) or
            dfs(r - 1, c, idx + 1) or
            dfs(r, c + 1, idx + 1) or
            dfs(r, c - 1, idx + 1)
        )

        # Restore
        board[r][c] = temp
        return found

    for r in range(m):
        for c in range(n):
            if dfs(r, c, 0):
                return True

    return False


board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
]
print(word_search(board, "ABCCED"))  # True
print(word_search(board, "SEE"))     # True
print(word_search(board, "ABCB"))    # False

---

11. Matrix Layer Rotation

def rotate_matrix_layers(matrix, r):
    """
    Rotate each layer of an m x n matrix by r positions.

    Used in problems like HackerRank Matrix Layer Rotation.
    """
    m, n = len(matrix), len(matrix[0])
    layers = min(m, n) // 2

    for layer in range(layers):
        # Extract the elements of this layer
        elements = []
        top, bottom = layer, m - 1 - layer
        left, right = layer, n - 1 - layer

        # Top row
        for c in range(left, right):
            elements.append(matrix[top][c])
        # Right column
        for row in range(top, bottom):
            elements.append(matrix[row][right])
        # Bottom row (reversed)
        for c in range(right, left, -1):
            elements.append(matrix[bottom][c])
        # Left column (reversed)
        for row in range(bottom, top, -1):
            elements.append(matrix[row][left])

        # Rotate elements
        perimeter = len(elements)
        shift = r % perimeter
        elements = elements[shift:] + elements[:shift]

        # Put elements back
        idx = 0
        for c in range(left, right):
            matrix[top][c] = elements[idx]
            idx += 1
        for row in range(top, bottom):
            matrix[row][right] = elements[idx]
            idx += 1
        for c in range(right, left, -1):
            matrix[bottom][c] = elements[idx]
            idx += 1
        for row in range(bottom, top, -1):
            matrix[row][left] = elements[idx]
            idx += 1

    return matrix

---

12. Practice Problems

Problem	Platform	Key Technique
Spiral Matrix (LC 54)	LeetCode	Layer-peeling spiral
Spiral Matrix II (LC 59)	LeetCode	Generate spiral
Rotate Image (LC 48)	LeetCode	Transpose + reverse
Set Matrix Zeroes (LC 73)	LeetCode	Marker technique
Search a 2D Matrix (LC 74)	LeetCode	Binary search
Search a 2D Matrix II (LC 240)	LeetCode	Staircase search
Diagonal Traverse (LC 498)	LeetCode	Zigzag diagonal
Word Search (LC 79)	LeetCode	DFS backtracking
Transpose Matrix (LC 867)	LeetCode	Basic transpose
Reshape the Matrix (LC 566)	LeetCode	Index mapping

---

Big-O Summary

Operation	Time	Space
Spiral traversal	O(mn)	O(1) extra
Diagonal traversal	O(mn)	O(1) extra
Rotate 90 degrees	O(n^2)	O(1) in-place
Transpose	O(mn)	O(mn) or O(1) for square
Set matrix zeroes	O(mn)	O(1) with markers
Staircase search	O(m+n)	O(1)
Binary search (sorted)	O(log(mn))	O(1)
Word search	O(mn * 4^L)	O(L) recursion

Matrix traversal problems are fundamentally about careful index management. Once you master spiral, diagonal, and rotation, most matrix problems become variations of these patterns.