Problem Statement in English

You’re given an $n \times n$ 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

Approach

The easiest way to rotate the image is to first transpose the matrix and then reverse each row.

And we’re done!

Solution in Python


class Solution:
    def rotate(self, mat: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        N = len(mat)
        for i in range(N):
                for j in range(i + 1, N):
                    mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
            
        for i in range(N):
            mat[i].reverse()

Complexity

  • Time: $O(n^2)$
    Since we traverse the entire matrix once.

  • Space: $O(1)$
    Since we do it in-place.

And we are done.