Matrix Rotation / Traversal

Matrix Rotation and Transformation

LeetCode 48. Rotate Image asks you to rotate an $n \times n$ matrix 90° clockwise in place. Rotating a matrix in-place is one of those problems that feels harder than it is. Once you see that a 90° clockwise rotation decomposes into two simple operations, a transpose followed by reversing each row, the implementation almost writes itself. Understanding why that decomposition works, and how it generalizes to other rotations, is what makes this pattern sticky.

The Core Insight: Transpose Then Reverse

A transpose swaps matrix[i][j] with matrix[j][i] for every pair where j > i. Visually, it reflects the matrix along its main diagonal, turning rows into columns and columns into rows.

A row reversal mirrors each row horizontally.

Applying both operations in sequence, transpose, then reverse each row, produces a 90° clockwise rotation. Here's why geometrically: in the original matrix, the element at row i, column j should land at row j, column (n-1-i) after a 90° clockwise rotation. The transpose moves (i, j) to (j, i). Reversing row j then moves column i to column (n-1-i). The two steps compose exactly to the rotation mapping.

Walking Through a $3 \times 3$ Example

Start with:

1 2 3
4 5 6
7 8 9

Step 1, Transpose (swap across the main diagonal):

1 4 7
2 5 8
3 6 9

Step 2, Reverse each row:

7 4 1
8 5 2
9 6 3

That is the correct 90° clockwise rotation. The top row (1, 2, 3) became the rightmost column, reading top to bottom. The left column (1, 4, 7) became the top row, reading left to right. Both are exactly what a 90° clockwise rotation requires.

The Code

def rotate_90_clockwise(matrix):
    n = len(matrix)
    # Transpose: swap matrix[i][j] with 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]
    # Reverse each row
    for row in matrix:
        row.reverse()

The transpose loop starts j at i + 1 to avoid redundant swaps and to prevent elements from being swapped back to their original positions. The row reversal is $O(n)$ per row. Total time is $O(n²)$. No extra space is needed beyond the two loop variables. The entire operation is in-place.

Counterclockwise Rotation

A 90° counterclockwise rotation maps (i, j) to (n-1-j, i). The decomposition here is: transpose, then reverse each column (i.e., reverse the order of rows). Alternatively, you can reverse each row first, then transpose; both sequences produce the same result.

def rotate_90_counterclockwise(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 columns by reversing the list of rows
    matrix.reverse()

matrix.reverse() reorders the rows in place. That's equivalent to reversing each column when viewed from the original orientation.

180° Rotation

A 180° rotation is simply two consecutive 90° rotations. In practice, it's easier to express directly: reverse each row, then reverse the list of rows (or reverse each column, then each row; both work).

def rotate_180(matrix):
    for row in matrix:
        row.reverse()
    matrix.reverse()

You can verify this with the $3 \times 3$ example: after two steps, the element at (0, 0) ends up at (n-1, n-1), and the element at (i, j) ends up at (n-1-i, n-1-j), the expected mapping for a 180° rotation.

In-Place vs. New Matrix for Non-Square Matrices

The transpose-based technique works only for square matrices (n × n), because the transpose requires matrix[i][j] and matrix[j][i] to both exist within the same structure. For a non-square m × n matrix, rotating 90° produces an n × m matrix. The dimensions themselves change, so in-place rotation is impossible without allocating a new matrix.

def rotate_90_clockwise_nonsquare(matrix):
    m, n = len(matrix), len(matrix[0])
    # Result is n rows by m columns
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][m - 1 - i] = matrix[i][j]
    return result

The mapping result[j][m-1-i] = matrix[i][j] is the direct formula for 90° clockwise rotation of a non-square matrix. Time and space are both $O(m \times n)$.

Layer-by-Layer Rotation

Some problems frame rotation as working ring by ring: the outermost ring, then the next ring inward, and so on. This is the perspective used in LeetCode 48. Rotate Image when solved without the transpose shortcut. Each layer is a sequence of four edges, and you rotate elements four at a time by cycling them: top → right → bottom → left → top.

def rotate_layer_by_layer(matrix):
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            offset = i - first
            # Save top
            top = matrix[first][i]
            # Left -> Top
            matrix[first][i] = matrix[last - offset][first]
            # Bottom -> Left
            matrix[last - offset][first] = matrix[last][last - offset]
            # Right -> Bottom
            matrix[last][last - offset] = matrix[i][last]
            # Top -> Right
            matrix[i][last] = top

This approach is more verbose than transpose + reverse, but it makes the rotation structure visible: n // 2 layers, each requiring last - first four-way swaps. The result is the same $O(n²)$ time and $O(1)$ space.

Set Matrix Zeroes

LeetCode 73. Set Matrix Zeroes asks: given an m × n matrix, if any cell is 0, set its entire row and column to 0. The naive approach uses $O(m + n)$ extra space to record which rows and columns need zeroing. The $O(1)$ space trick is to use the first row and first column of the matrix itself as markers.

First, check whether the first row or first column originally contains any zeros (store this in two booleans). Then scan the rest of the matrix: if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0. In a second pass, use those markers to zero out the interior. Finally, zero out the first row and/or first column if the booleans say so.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    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))
    # Mark
    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 interior using 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 and column
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

Time is $O(m \times n)$, space is $O(1)$. The order matters: zero the interior before touching the first row/column, otherwise you destroy your markers.

Game of Life

LeetCode 289. Game of Life requires updating every cell simultaneously based on its current neighbors (alive = 1, dead = 0). If you update cells one at a time, later cells see partially-updated state. The in-place trick is to encode transitions using extra bits so the original state remains readable:

• 0 → 0: stays 0 (no change needed).
• 1 → 0: encode as 2 ("was alive, now dead").
• 0 → 1: encode as 3 ("was dead, now alive").
• 1 → 1: stays 1 (no change needed).

When counting live neighbors, treat values 1 and 2 as alive (both were alive in the original state). After the full pass, convert: replace 2 with 0 and 3 with 1.

def gameOfLife(board):
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            live = 0
            for di in (-1, 0, 1):
                for dj in (-1, 0, 1):
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and board[ni][nj] in (1, 2):
                        live += 1
            if board[i][j] == 1 and (live < 2 or live > 3):
                board[i][j] = 2  # alive -> dead
            elif board[i][j] == 0 and live == 3:
                board[i][j] = 3  # dead -> alive
    for i in range(m):
        for j in range(n):
            if board[i][j] == 2:
                board[i][j] = 0
            elif board[i][j] == 3:
                board[i][j] = 1

Time is $O(m \times n)$, space is $O(1)$. The encoding trick generalizes to any cellular automaton where you need to apply updates simultaneously without an auxiliary grid.

Complexity

All in-place square-matrix rotations run in $O(n²)$ time and $O(1)$ extra space. For non-square matrices that require a new result matrix, space is $O(m \times n)$. The transpose + reverse decomposition is generally the cleanest implementation path for square matrices and is worth memorizing as the default approach.

Recognizing this pattern

You're probably looking at matrix rotation/traversal when:

• The problem says "rotate the image" or "rotate the matrix by 90 degrees", typically with an in-place / $O(1)$ space constraint.
• You need spiral, diagonal, or boundary traversal in a fixed order.
• The operation is a permutation of cell positions: anything expressible as transpose + row reverse + column reverse.
• The problem asks to apply updates simultaneously across the grid (next state depends only on current state) without an auxiliary grid.

Common templates:

• Transpose + reverse rows: the canonical 90° clockwise in-place rotation. Example: Rotate Image.
• Spiral traversal with four moving bounds: shrink top/bottom/left/right after each side. Example: Spiral Matrix.
• Encode auxiliary state in unused values: mark first row/column as a "this row/column is zero" flag, then write back in a second pass. Example: Set Matrix Zeroes.
• Two-bit cell encoding for simultaneous updates: store old and new state in the same cell, decode after one full pass. Example: Game of Life.
• Layer-by-layer 4-way cycle: rotate one ring at a time using a single temp. Example: Rotate Image.