Rotate Image

You are given an n x n matrix. Rotate it 90 degrees clockwise in-place.

Why this is worth learning

Compose two easy coordinate transformations instead of memorizing a four-way cycle. A clockwise rotation maps original (r,c) to (c,n-1-r).

Before coding: one-minute experiment

In a 3-by-3 matrix, where does the original cell (2,0) move after a clockwise rotation?

Function signature

func RotateImage(matrix [][]int)

Inputs / outputs

• matrix: square matrix to rotate in-place.
• Return: nothing; modify matrix.

Example

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
After rotation:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Constraints

• 1 <= n <= 1000

Core idea (near-solution)

Rotate in-place using two steps:

1. Transpose the matrix (swap matrix[i][j] with matrix[j][i]).
2. Reverse each row.

This is equivalent to a 90-degree clockwise rotation.

Invariant: after transposing, rows become columns; reversing rows completes the rotation.

Algorithm (step-by-step)

1. For each i in [0..n-1]:
   • For each j in [i+1..n-1], swap matrix[i][j] and matrix[j][i].
2. For each row, reverse it in-place.

Correctness sketch

Transposition sends the value at (r,c) to (c,r). Swapping only positions with c>r performs each off-diagonal exchange exactly once and leaves the diagonal unchanged. Reversing each transposed row then maps (c,r) to (c,n-1-r), which is the clockwise-rotation formula. Both transformations are permutations, so no value is lost or duplicated. Their composition therefore places every original cell at exactly its required destination. All exchanges occur in the original matrix with constant auxiliary state.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
After rotation:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Walk:
- transpose -> [[1,4,7],[2,5,8],[3,6,9]]
- reverse each row -> [[7,4,1],[8,5,2],[9,6,3]]

Pitfalls to avoid

• Transposing twice or reversing columns instead of rows.
• Using extra matrices (violates in-place requirement).

Debugging lens

Test an asymmetric numbered square. Four rotations returning to the original is useful but not enough: a no-op also passes that property. Check the coordinate mapping after one rotation.

Complexity

• Time: O(n^2)
• Extra space: O(1)

Implementation notes (Go)

• Transpose the matrix, then reverse each row in place.
• Only swap cells where c > r to avoid double-swaps.

Reconstruction checkpoint

In a 3-by-3 matrix, where does the original cell (2,0) move after a clockwise rotation?

Return to Matrix · Module quiz