Image Rotation

1. Background Knowledge

Rotating an n × n matrix 90° clockwise in-place is a classic array manipulation problem in computer science, rooted in matrix transposition and row reversal. For a position (i, j) in the original matrix, the rotated position is (j, n-1-i).

Key mathematical insight: A 90° clockwise rotation can be decomposed into:

1. Transpose the matrix (swap matrix[i][j] ↔ matrix[j][i])
2. Reverse each row (flip left-to-right)

This works because:

Original: matrix[i][j] → rotated[j][n-1-i]
Transpose: matrix[i][j] → matrix[j][i]
Reverse: matrix[j][i] → matrix[j][n-1-i] ✓

No diagrams from papers directly illustrate this exact algorithm (search results focus on advanced rotation-invariant CNNs and computer vision), but the concept aligns with basic linear algebra transformations used in image processing.

Prerequisites:

• 2D array indexing and bounds checking
• In-place swapping (constant extra space)
• Understanding square matrices (n × n)

2. Algorithm Approach

The optimal in-place algorithm uses transposition + reversal:

Step 1: Transpose (upper triangle only to avoid double-swapping)
for i from 0 to n-2:
 for j from i+1 to n-1:
 swap(matrix[i][j], matrix[j][i])

Step 2: Reverse each row
for i from 0 to n-1:
 reverse matrix[i] (swap 0↔n-1, 1↔n-2,...)

Alternative approach: Direct 4-way cycle swapping (visits each cycle once):

for i from 0 to n/2-1:
 for j from i to n-i-2:
 # Cycle: (i,j) → (j,n-1-i) → (n-1-i,n-1-j) → (n-1-j,i)
 temp = matrix[i][j]
 matrix[i][j] = matrix[n-1-j][i]
 matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
 matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
 matrix[j][n-1-i] = temp

Both achieve O(n²) time with O(1) space.

3. Step-by-Step Strategy

1. Validate input: Ensure n ≥ 1 and matrix is square.
2. Handle base case: If n == 1, return (no rotation needed).
3. Execute transpose:

for i in range(n):
for j in range(i+1, n): # Avoid diagonal & duplicates
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

4. Reverse rows:

for i in range(n):
matrix[i].reverse() # Or manual left-right swaps

5. Verify: Test with small examples (n=2, n=3).

Example (n=3):

Input:
1 2 3
4 5 6
7 8 9

After transpose:
1 4 7
2 5 8
3 6 9

After row reverse:
7 4 1
8 5 2
9 6 3 ✓ (90° clockwise)

Complete Python code:

def rotate(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 rows
 for i in range(n):
 matrix[i].reverse()

4. Common Pitfalls

• Double-swapping in transpose: Swapping (i,j) and (j,i) twice if looping j=0 to n-1. Fix: Loop j=i+1 to n-1.
• Ignoring center in odd n: For n=3, center (1,1) stays fixed—transpose+reverse handles automatically.
• Out-of-bounds: Ensure indices stay within [0,n-1].
• Non-square matrices: Constraints guarantee n×n, but validate anyway.
• Mutable vs immutable: Languages like Python lists are mutable; Java arrays need care with references.
• Floating-point precision: Elements can be floats, but swapping preserves exact values.

5. Time & Space Complexity

Why optimal? Must read/write all $n^2$ elements; in-place constraint limits space to O(1).

This approach is production-ready, used in LeetCode #48 (Rotate Image) and image processing pipelines.