Introduction
Rotating a 2D matrix by 90 degrees is a common programming problem that involves transforming the rows and columns of a matrix. This operation is useful in:
- Image processing (rotating images)
- Game development (rotating game boards)
- Computer graphics
- Matrix transformations
There are two types of rotations:
1. Clockwise rotation - Rotate to the right by 90 degrees
2. Anticlockwise rotation - Rotate to the left by 90 degrees
Problem Statement
Given an N x N 2D matrix, rotate it by 90 degrees (clockwise or anticlockwise).
Example:
Original Matrix:
1 2 3
4 5 6
7 8 9
After 90° Clockwise Rotation:
7 4 1
8 5 2
9 6 3
After 90° Anticlockwise Rotation:
3 6 9
2 5 8
1 4 7
Approach & Explanation
Method 1: Transpose + Reverse (Clockwise Rotation)
To rotate a matrix 90 degrees clockwise:
Step 1: Transpose the matrix
- Convert rows to columns
- Element at position [i][j] moves to [j][i]
Step 2: Reverse each row
- Reverse the order of elements in each row
Example:
Original: Transpose: Reverse Rows:
1 2 3 1 4 7 7 4 1
4 5 6 → 2 5 8 → 8 5 2
7 8 9 3 6 9 9 6 3
Method 2: Transpose + Reverse (Anticlockwise Rotation)
To rotate a matrix 90 degrees anticlockwise:
Step 1: Transpose the matrix
- Convert rows to columns
Step 2: Reverse each column
- Reverse the order of elements in each column
Code Implementation
Clockwise Rotation (90 degrees)
def rotate_matrix_clockwise(matrix):
"""
Rotate a 2D matrix 90 degrees clockwise
Args:
matrix: 2D list (N x N matrix)
Returns:
Rotated matrix
"""
n = len(matrix)
# Step 1: Transpose the matrix
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each row
for i in range(n):
matrix[i].reverse()
return matrix
# Test the function
matrix1 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("Original Matrix:")
for row in matrix1:
print(row)
rotate_matrix_clockwise(matrix1)
print("\nAfter 90° Clockwise Rotation:")
for row in matrix1:
print(row)
Anticlockwise Rotation (90 degrees)
def rotate_matrix_anticlockwise(matrix):
"""
Rotate a 2D matrix 90 degrees anticlockwise
Args:
matrix: 2D list (N x N matrix)
Returns:
Rotated matrix
"""
n = len(matrix)
# Step 1: Transpose the matrix
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each column (reverse the matrix vertically)
for j in range(n):
for i in range(n // 2):
matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]
return matrix
# Test the function
matrix2 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("\nOriginal Matrix:")
for row in matrix2:
print(row)
rotate_matrix_anticlockwise(matrix2)
print("\nAfter 90° Anticlockwise Rotation:")
for row in matrix2:
print(row)
Alternative: Using Python List Comprehension
def rotate_clockwise_compact(matrix):
"""Compact version using list comprehension"""
n = len(matrix)
return [[matrix[n - 1 - j][i] for j in range(n)] for i in range(n)]
def rotate_anticlockwise_compact(matrix):
"""Compact version using list comprehension"""
n = len(matrix)
return [[matrix[j][n - 1 - i] for j in range(n)] for i in range(n)]
# Test compact versions
matrix3 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
print("\nOriginal 4x4 Matrix:")
for row in matrix3:
print(row)
result = rotate_clockwise_compact(matrix3)
print("\nClockwise Rotation:")
for row in result:
print(row)
Output
Original Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
After 90° Clockwise Rotation:
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
Original Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
After 90° Anticlockwise Rotation:
[3, 6, 9]
[2, 5, 8]
[1, 4, 7]
Original 4x4 Matrix:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]
Clockwise Rotation:
[13, 9, 5, 1]
[14, 10, 6, 2]
[15, 11, 7, 3]
[16, 12, 8, 4]
Complexity Analysis
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Transpose | O(n²) | O(1) |
| Reverse Rows/Columns | O(n²) | O(1) |
| Total | O(n²) | O(1) |
Where:
- n = size of the matrix (n x n)
Note: The in-place rotation modifies the original matrix. If you need to preserve the original, create a copy first.
Key Takeaways
- Clockwise rotation = Transpose + Reverse each row
- Anticlockwise rotation = Transpose + Reverse each column
- Both rotations can be done in-place without extra space
- The algorithm works for any N x N matrix
- Rotate by 180° = Apply 90° rotation twice
- Rotate by 270° clockwise = Rotate by 90° anticlockwise
Important Points
- The matrix must be square (N x N) for this approach
- For rectangular matrices, you need a different approach
- Multiple 90° rotations:
- 2 rotations = 180°
- 3 rotations = 270°
- 4 rotations = back to original
Practice Problems
Try these variations:
- Rotate matrix by 180 degrees
- Rotate rectangular matrix (M x N)
- Rotate matrix by any angle (45°, 270°, etc.)
- Rotate image represented as 2D array
Complexity Analysis
- Time Complexity: O(N*M) where N and M are matrix dimensions.
- Space Complexity: O(1) if rotated in-place, or O(N*M) for a new matrix.