Rotate Image

Problem Statement

Given a square n x n matrix of integers matrix, rotate it by 90 degrees clockwise.

You must rotate the matrix in-place. Do not allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [
  [1,2],
  [3,4]
]


Output: [
  [3,1],
  [4,2]
]

Example 2:

Input: matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]


Output: [
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

You should aim for a solution with O(n^2) time and O(1) space, where n is the length of the matrix.

Hint 1

Consider the properties of the rotated matrix. How are the elements rearranged?

Hint 2

Can you perform the rotation in-place by swapping elements?

Hint 3

Think about reversing the matrix and then transposing it.

Solution

Brute Force

def rotate_brute_force(matrix: list[list[int]]) -> None:
    """
    Rotates the matrix by creating a new matrix.
    """
    n = len(matrix)
    rotated = [[0] * n for _ in range(n)]


    for i in range(n):
        for j in range(n):
            rotated[j][n - 1 - i] = matrix[i][j]


    for i in range(n):
        for j in range(n):
            matrix[i][j] = rotated[i][j]

Time complexity: O(n ^ 2) Space complexity: O(n ^ 2)

Rotate By Four Cells

def rotate_four_cells(matrix: list[list[int]]) -> None:
    """
    Rotates the matrix by swapping four cells at a time.
    """
    l, r = 0, len(matrix) - 1
    while l < r:
        for i in range(r - l):
            top, bottom = l, r


            # save the topleft
            top_left = matrix[top][l + i]


            # move bottom left into top left
            matrix[top][l + i] = matrix[bottom - i][l]


            # move bottom right into bottom left
            matrix[bottom - i][l] = matrix[bottom][r - i]


            # move top right into bottom right
            matrix[bottom][r - i] = matrix[top + i][r]


            # move top left into top right
            matrix[top + i][r] = top_left
        r -= 1
        l += 1

Time complexity: O(n ^ 2) Space complexity: O(1)

Reverse And Transpose

def rotate_reverse_transpose(matrix: list[list[int]]) -> None:
    """
    Rotates the matrix by reversing and then transposing it.
    """
    # Reverse the matrix vertically
    matrix.reverse()


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

Time complexity: O(n ^ 2) Space complexity: O(1)