Introduction
LeetCode 48: Rotate Image challenges you to rotate a square matrix 90 degrees clockwise in-place. This means that the matrix must be modified without using an additional matrix for storage.
It’s a classic problem to test your understanding of 2D matrix manipulation and in-place operations. A smart approach combines transpose and reverse techniques to solve it efficiently.
Problem Statement
You are given an n x n 2D matrix representing an image. Rotate the image in-place by 90 degrees (clockwise).
Example 1:
go
Input: matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output: [
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
go
Input: matrix = [
[5,1,9,11],
[2,4,8,10],
[13,3,6,7],
[15,14,12,16]
]
Output: [
[15,13,2,5],
[14,3,4,1],
[12,6,8,9],
[16,7,10,11]
]
Constraints
- Matrix size is
n x n (square matrix).
- Rotate the matrix in-place, i.e., do not allocate another matrix.
Approach: Transpose + Reverse Each Row
To rotate the matrix 90° clockwise in-place, we follow two key steps:
1. Transpose the Matrix
Convert rows to columns:
matrix[i][j] becomes matrix[j][i]- Only transpose elements above the diagonal to avoid double swapping.
2. Reverse Each Row
After transposing, each row is reversed to complete the 90-degree clockwise rotation.
Go Implementation
go
func rotate(matrix [][]int) {
n := len(matrix)
// Step 1: Transpose the matrix
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
// Step 2: Reverse each row
for i := 0; i < n; i++ {
for j := 0; j < n/2; j++ {
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
}
}
}
Example Walkthrough
Let's walk through a 3x3 matrix:
Input:
csharp
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
Step 1 - Transpose:
Swap elements across the diagonal.
csharp
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]
Step 2 - Reverse Rows:
csharp
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
This is the final rotated matrix.
Time and Space Complexity
MetricComplexityTime ComplexityO(n²)Space ComplexityO(1)
- Time Complexity: We visit each element once during the transpose and once again during the reverse step → O(n²).
- Space Complexity: The operation is done in-place without extra storage → O(1).
Edge Cases
- 1x1 Matrix:
- Input:
[[1]]
- Output:
[[1]] (no change)
- Even/Odd sized square matrices: Both are supported.
- Empty Matrix: As per constraints, input is always a valid square matrix.
Key Takeaways
- Matrix rotation can be elegantly handled using transpose + reverse strategies.
- Avoid extra space by modifying the matrix directly using Go’s built-in slice swapping.
- Understand in-place transformations for efficient memory usage—commonly asked in interviews.