Problem
Given an n × n matrix representing an image, rotate it 90 degrees clockwise. The rotation must happen in place, without allocating another matrix.
Approach
A clockwise rotation is the same as two simple steps: transpose the matrix by swapping it across its main diagonal, then reverse each row.
Only swap the cells above the diagonal during the transpose. Swapping every pair would put each one back where it started.
Solution
class Solution:
def rotate(self, matrix: list[list[int]]) -> None:
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()Complexity
- Time: O(n²): every cell moves a constant number of times.
- Space: O(1).
Edge cases
- A 1 × 1 matrix stays the same.
- Odd sizes have a centre cell that never moves.
- Rotating anticlockwise instead reverses each row first, then transposes.