The problem
Rotate an n × n matrix a quarter turn clockwise, changing it in place — without building a second matrix.
Examples
01
- Input
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
- Output
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
02
- 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]]
Constraints
- 1 ≤ n ≤ 20
- −1000 ≤ matrix[i][j] ≤ 1000
The idea
A quarter turn clockwise sends the cell in row r, column c to row c, column n − 1 − r. That move is two simpler ones in a row.
First flip the matrix across its main diagonal (top-left to bottom-right) — swap [r][c] with [c][r], which sends (r, c) to (c, r). Then reverse every row, which sends column r to column n − 1 − r. Together: (r, c) → (c, n − 1 − r). Both steps are swaps, so nothing extra is stored.
- Time
- O(n²)
- Space
- O(1)
Solution · every language run against every case
class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # A quarter turn clockwise is a flip across the main diagonal, then each row reversed. 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()