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
Recommended Time and Space Complexity
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)