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.
Brute force
We can keep swapping elements one-by-one, layer-by-layer, as long as we can find the coordinates of each of the four items.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n//2):
for j in range(i,n-i-1):
matrix[i][j],matrix[j][n-i-1],matrix[n-i-1][n-j-1],matrix[n-j-1][i]=\
matrix[n-j-1][i],matrix[i][j],matrix[j][n-i-1],matrix[n-i-1][n-j-1]
More elegently
Suggested by @shichaotan, here’s another way of rotating the matrix clockwise: we would first reverse the matrix upside-down and then swap the symmetry.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
matrix.reverse()
for i in range(len(matrix)):
for j in range(i):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
Similarly, if we want to rotate an image anti-clockwise, we can first reverse the matrix left to right and then swap the symmetry.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
for e in matrix:
e.reverse()
for i in range(len(matrix)):
for j in range(i):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]