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 the x or y 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
        """

Leetcode 48 Rotate Image