Rotate Image [Solution]

This exercise assesses the your ability to manipulate matrices, work with indices, and perform in-place modifications efficiently.

Solution 1

This solution first transposes the matrix by swapping elements across the main diagonal. Then, it reverses each row to achieve the 90-degree clockwise rotation.

Below is a Python implementation of the rotate function to rotate a given matrix by 90 degrees clockwise in-place:

from typing import List

def rotate(matrix: List[List[int]]) -> None:
    n = len(matrix)

    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

# Example usage:
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

rotate(matrix)
print(matrix)

Time Complexity:

The time complexity of this solution is O(n^2), where n is the number of rows or columns in the matrix.

Space Complexity:

The space complexity is O(1) since the rotation is done in-place without using extra space.

Solution 2

There is a more intuitive solution that maps the index one by one. However, it is less space-efficient, with a space complexity of O(n^2).

from typing import List

def rotate(matrix: List[List[int]]) -> None:
    n = len(matrix)

    # Rotate the matrix
    result = [[0 for i in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            result[i][j] = matrix[n-1-j][i]
    
    # Put it back
    for i in range(n):
        for j in range(n):
            matrix[i][j] = result[i][j]