Rotate Image
- 2 min read
- LC-Medium
- Math-and-geometry
3 years ago
Solution 1
- Just have 4 pointers: left, right, top, bottom
- Do a while loop
while l < r- In loop, initialize top and bottom to
landr - Do a for loop with
i, and add / subtractiwherever necessary to indicate moving on to the next row/column - At the end, change
landrpointers to move inwards- Since we're initializing
tandbwithlandr, no need to implicitly changelandr
- Since we're initializing
- In loop, initialize top and bottom to
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) | where n is the size of the matrix |
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
l, r = 0, len(matrix) - 1
while l < r:
t, b = l, r
for i in range(r - l):
top_left = matrix[t][l + i]
matrix[t][l + i] = matrix[b - i][l]
matrix[b - i][l] = matrix[b][r - i]
matrix[b][r - i] = matrix[t + i][r]
matrix[t + i][r] = top_left
l += 1
r -= 1
Solution 2 (Transpose + Reverse)
- Although has same time complexity, this approach does twice as many reads and writes. But it's much easier to visualize
- First, transpose matrix.
- Then reverse each row, not column.
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# Transpose
n = len(matrix)
for r in range(n):
for c in range(r + 1, n):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
# Reverse
for row in range(n):
l, r = 0, n - 1
while l < r:
matrix[row][l], matrix[row][r] = matrix[row][r], matrix[row][l]
l += 1
r -= 1