MediumBlind75MatrixMath
Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise) in-place.
Examples
Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output
[[7,4,1],[8,5,2],[9,6,3]]
Rotate 90 degrees clockwise.
Input
matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output
[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Rotate 90 degrees clockwise.
Constraints
- •
n == matrix.length == matrix[i].length - •
1 <= n <= 20 - •
-1000 <= matrix[i][j] <= 1000
Approaches
Create a new matrix and copy rotated values.
CodeT: O(n^2) | S: O(n^2)
def rotate(matrix):
n = len(matrix)
temp = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
temp[j][n - 1 - i] = matrix[i][j]
for i in range(n):
for j in range(n):
matrix[i][j] = temp[i][j]First transpose the matrix, then reverse each row.
CodeT: O(n^2) | S: O(1)
def rotate(matrix):
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()Rotate four cells at a time, layer by layer from outside in.
Diagram
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Transpose: [[1,4,7],[2,5,8],[3,6,9]]
Reverse rows: [[7,4,1],[8,5,2],[9,6,3]]
CodeT: O(n^2) | S: O(1)
def rotate(matrix):
n = len(matrix)
for layer in range(n // 2):
first = layer
last = n - 1 - layer
for i in range(first, last):
offset = i - first
top = matrix[first][i]
matrix[first][i] = matrix[last - offset][first]
matrix[last - offset][first] = matrix[last][last - offset]
matrix[last][last - offset] = matrix[i][last]
matrix[i][last] = topComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - Extra Matrix | O(n^2) | O(n^2) | Create a new matrix and copy rotated values. |
| Transpose + Reverse | O(n^2) | O(1) | First transpose the matrix, then reverse each row. |
| Layer by Layer | O(n^2) | O(1) | Rotate four cells at a time, layer by layer from outside in. |
Brute Force - Extra Matrix
T: O(n^2)S: O(n^2)
Create a new matrix and copy rotated values.
Transpose + Reverse
T: O(n^2)S: O(1)
First transpose the matrix, then reverse each row.
Layer by Layer
T: O(n^2)S: O(1)
Rotate four cells at a time, layer by layer from outside in.
Common Mistakes
Using extra space when O(1) is required
Not handling the transpose correctly (swapping only upper triangle)
Confusing clockwise with counter-clockwise rotation