01.07. Rotate Matrix

Description

Given an image represented by an N x N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

 

Example 1:

Given matrix =

[

  [1,2,3],

  [4,5,6],

  [7,8,9]

],



Rotate the matrix in place. It becomes:

[

  [7,4,1],

  [8,5,2],

  [9,6,3]

]

Example 2:

Given matrix =

[

  [ 5, 1, 9,11],

  [ 2, 4, 8,10],

  [13, 3, 6, 7],

  [15,14,12,16]

],



Rotate the matrix in place. It becomes:

[

  [15,13, 2, 5],

  [14, 3, 4, 1],

  [12, 6, 8, 9],

  [16, 7,10,11]

]

Solutions

Solution 1: In-place Rotation

According to the problem requirements, we actually need to rotate $matrix[i][j]$ to $matrix[j][n - i - 1]$.

We can first flip the matrix upside down, that is, swap $matrix[i][j]$ and $matrix[n - i - 1][j]$, and then flip the matrix along the main diagonal, that is, swap $matrix[i][j]$ and $matrix[j][i]$. This way, we can rotate $matrix[i][j]$ to $matrix[j][n - i - 1]$.

The time complexity is $O(n^2)$, where $n$ is the side length of the matrix. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptRustJavaScriptC#Swift

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n >> 1):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;