[Leetcode]48. Rotate Image

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

Swap one-by-one, layer-by-layer.

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.

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.

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]

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments