Rotate Image
Transpose then reverse each row — a 90-degree clockwise rotation in O(1) extra space.
2 min read
matrix in-place
Problem#
Rotate an n x n 2D matrix 90 degrees clockwise, in place.
Examples#
[[1,2,3],[4,5,6],[7,8,9]]→[[7,4,1],[8,5,2],[9,6,3]][[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]→[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints#
n == matrix.length == matrix[i].length,1 <= n <= 20.
Approach#
First transpose (swap matrix[i][j] with matrix[j][i] for j > i), then reverse each row. The composition is identical to a 90-degree clockwise rotation.
Solution#
class Solution {public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) swap(matrix[i][j], matrix[j][i]); for (auto& row : matrix) reverse(row.begin(), row.end()); }};func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } for _, row := range matrix { lo, hi := 0, len(row)-1 for lo < hi { row[lo], row[hi] = row[hi], row[lo] lo++ hi-- } }}from typing import List
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()function rotate(matrix) { const n = matrix.length; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } for (const row of matrix) row.reverse();}class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } } for (int[] row : matrix) { int lo = 0, hi = row.length - 1; while (lo < hi) { int tmp = row[lo]; row[lo++] = row[hi]; row[hi--] = tmp; } } }}function rotate(matrix: number[][]): void { const n = matrix.length; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } for (const row of matrix) row.reverse();}Editorial#
Transpose flips across the main diagonal; reversing each row then mirrors horizontally. Geometrically, a diagonal flip followed by a horizontal flip equals a 90-degree clockwise rotation.
Complexity#
- Time: O(n^2).
- Space: O(1).
Concept revision#
Related#