Rotate Image/Matrix

Arrangement

Problem

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.

For example:

Thought Process

• All rotations are essentially composite reflections (A composite transformation is when two or more transformations are combined to form a new image from the preimage); in this case, a reflection across the diagonal line of symmetry, then a reflection across the vertical line of symmetry.

• Notice how we can trasform each row of the matrix into a corresponding column (i.e. the diagonal transofrmation)

• After transforming the rows to columns, we can flip the columns in a horizontal fashion (i.e. across the vertical line of symmetry)

• It is important to consider when swapping horizontally, you only go until the halfway point of each row.

Solution

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:

        N = len(matrix[0])
        
        
        #turning rows in columns (reflection across 
        #diagonal)
        for i in range(len(matrix)):
            for j in range(i,len(matrix[0])):
                temp = matrix[j][i]
                matrix[j][i] = matrix[i][j]
                matrix[i][j] = temp
                
        #flipping across the vertical line of symmetry
        for i in range(len(matrix)):
            for j in range(len(matrix[0])//2):
                temp = matrix[i][N-1-j] #gets the postion on the opposite end
                matrix[i][N-1-j] = matrix[i][j]
                matrix[i][j] = temp
        print(matrix)

Key Facts

• We are transforming each row in the source matrix to the required column in the final matrix

• We are turning corresponding rows into columns with a reflection across the diagonal. We are then performing a reflection across the vertical to flip the elements horizontally in each row.

  • Turning rows into columns - swap(array[i][j], array[j][i]

  • Horizontally flipping - swap(array[i][j], array[i][N - 1 - j]

Time Complexity

• Time: $O(n^2)$

• Space: $O(1)$