Rotate Image
You're given an n x n matrix representing an image. Rotate it 90 degrees clockwise in place, so the first row becomes the last column. Change the input matrix directly without allocating a second matrix.
Examples
matrix = [[1,2],[3,4]] returns [[3,1],[4,2]]
The top row 1, 2 becomes the right column, read top to bottom.
matrix = [[2,4,6],[8,10,12],[14,16,18]] returns [[14,8,2],[16,10,4],[18,12,6]]
The first column, read bottom to top, becomes the first row. The center value 10 stays put.
matrix = [[5]] returns [[5]]
A single cell is unchanged by rotation.
Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Hints
Work out where the cell at row r, column c ends up after a clockwise turn.
The rotation splits into two operations you can each do with swaps: a reflection across the main diagonal and a reflection left to right.
Transpose by swapping matrix[r][c] and matrix[c][r] for c > r, then reverse every row.
Drill This: Your Approach First
Approach
A clockwise rotation sends the cell at (r, c) to (c, n - 1 - r). That move is two simpler in-place steps: transpose the matrix by swapping matrix[r][c] with matrix[c][r] for every c > r, then reverse each row. Both steps only swap pairs, so no second matrix is needed. O(n^2) time, O(1) extra space.
Time
O(n^2)
Space
O(1)
Pitfall
Solutions
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int r = 0; r < n; r++) {
for (int c = r + 1; c < n; c++) {
int t = matrix[r][c];
matrix[r][c] = matrix[c][r];
matrix[c][r] = t;
}
}
for (int[] row : matrix) {
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = row[i];
row[i] = row[j];
row[j] = t;
}
}
}
}class Solution:
def rotate(self, matrix) -> None:
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]
for row in matrix:
row.reverse()