Problem Statement
You are given an n x n
2D matrix
representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = \
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
Example 2:
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]
]
Key Insights
| (0,0) (0,1) (0,2) | | (1,0) (1,1) (1,2) | | (2,0) (2,1) (2,2) |
The trick to this problem is noticing that the transpose about the primary diagonal can be accomplished by swapping the row and column indexes:
(0, 1) ⟷ (1, 0)
. Once you notice this, you can then use reflections about thex
ory
axis to achieve the desired in-place rotation.
Array: Rotate 90° Clockwise
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# Transpose about primary diagonal
for r in range(n):
for c in range(r+1):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
# Reflect about y-axis
for r in range(n):
for c in range(n//2):
matrix[r][c], matrix[r][-1-c] = matrix[r][-1-c], matrix[r][c]
# Rotate 90 degress to the right
"""
Original Transposed Reflection about y
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
"""
Array: Rotate 90° Counterclockwise
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# Transpose about primary diagonal
for r in range(n):
for c in range(r+1):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
# Reflect about x-axis
for c in range(n):
for r in range(n//2):
matrix[r][c], matrix[-1-r][c] = matrix[-1-r][c], matrix[r][c]
# Rotate 90 degress to the left
"""
Original Transposed Reflection about x
1 2 3 1 4 7 3 6 9
4 5 6 ---> 2 5 8 ---> 2 5 8
7 8 9 3 6 9 1 4 7
"""