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)