Image Rotation

easyFREEImage manipulationLinear AlgebraCV - DSA

Implement an image rotation algorithm to rotate an $n \times n$ 2D matrix representing an image by 90 degrees in the clockwise direction. The image must be rotated in-place, meaning the input 2D matrix is modified directly without allocating additional memory. Return the rotated matrix.

The concept of image rotation is fundamental in image manipulation and computer vision, as it allows for the transformation of images to achieve desired orientations. This process involves applying a transformation matrix to the original image, which can be represented mathematically using linear algebra and matrix operations.

For a $2 \times 2$ image, a clockwise rotation looks like this:

\begin{pmatrix} a & b \\ c & d \end{pmatrix} \rightarrow \begin{pmatrix} c & a \\ d & b \end{pmatrix}

This technique is widely used in image processing applications.

Example

Input

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

Output

[[7,4,1],[8,5,2],[9,6,3]]

Reasoning

matrix is a $3 \times 3$ grid of pixel values: the top row is $1, 2, 3$ , the middle row $4, 5, 6$ , the bottom row $7, 8, 9$ .
A clockwise quarter turn tips the left edge up into the top edge, so the left column read from bottom to top, $7, 4, 1$ , becomes the new top row.
The same happens to the middle column ( $8, 5, 2$ becomes row 2) and the right column ( $9, 6, 3$ becomes row 3), giving [[7,4,1],[8,5,2],[9,6,3]].
In general, the value at row $r$ , column $c$ (counting from 1) lands at row $c$ , column $n + 1 - r$ . Check with $7$ : it starts at row 3, column 1 and lands at row 1, column $3 + 1 - 3 = 1$ .
Notice the four corners trade places in a cycle ( $1$ goes top-right, $3$ bottom-right, $9$ bottom-left, $7$ top-left) while the centre $5$ stays put. The result keeps its $n \times n$ shape.

Constraints

1 <= n, m <= 100; Elements of matrix and vector can be integers or floats.

More from CV - DSA

Concept primer

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:

Transpose the matrix (swap matrix[i][j] ↔ matrix[j][i])
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

Validate input: Ensure n ≥ 1 and matrix is square.
Handle base case: If n == 1, return (no rotation needed).
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]

Reverse rows:

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

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

Aspect	Complexity	Explanation
Time	O(n²)	Visits each of n² elements exactly once (transpose: ~n²/2 swaps, reverse: n²/2 swaps)
Space	O(1)	Only uses 1-4 temporary variables for swapping; no extra matrix

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.

solution.py

Python 3.13

Test results