Rotate Image – Solution & Complexity

• You must rotate an n x n matrix 90 degrees clockwise.
• A naive approach allocates a brand new matrix and copies each cell to its rotated position — simple to reason about, but uses O(n^2) extra space.
• The interesting version of this problem does it in place with only O(1) extra space, which is what most interviewers are really asking for.

• Rotating 90 degrees clockwise can be decomposed into two simpler, well-known in-place operations:
  1. Transpose the matrix (swap matrix[i][j] with matrix[j][i] for all i < j) — this flips the matrix across its main diagonal.
  2. Reverse each row — this mirrors every row horizontally.
• Doing both in sequence produces exactly the 90-degree clockwise rotation, using only the original array's memory.

• After transposing, matrix[i][j] holds the original matrix[j][i]. The first column now reads top-to-bottom as the original first row read left-to-right.
• Reversing each row then flips that column's order, which is exactly what a clockwise rotation does: the original first row becomes the new last column, read top-to-bottom.
• Trace on [[1,2,3],[4,5,6],[7,8,9]]: transpose gives [[1,4,7],[2,5,8],[3,6,9]]; reversing each row gives [[7,4,1],[8,5,2],[9,6,3]] — the correct rotation.

Both the transpose and the row-reversal are O(n^2) (every cell is touched once), giving O(n^2) time and O(1) extra space overall — optimal, since you must write every one of the n^2 output cells.

• Transposing the full matrix (both i < j and i > j) undoes itself — only swap the upper triangle (j > i) once.
• Reversing columns instead of rows, or transposing across the anti-diagonal instead of the main diagonal, produces a counter-clockwise rotation or a flip instead of the required clockwise rotation.
• Follow-ups: how would you rotate 90 degrees counter-clockwise (reverse columns/rows in a different order)? How would you handle a non-square m x n matrix, where true in-place rotation isn't possible without extra bookkeeping?