Rotate Image

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

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

• Invariant: after transposing, rows become columns; reversing rows completes the rotation.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

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

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.