Problem
You are given ann Ć n 2D matrix representing an image. Rotate the image by 90 degrees clockwise.
The rotation must be performed in-place, meaning you cannot use another matrix to store the result.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
matrix = [ [1,2,3], [4,5,6], [7,8,9] ]Output
[ [7,4,1], [8,5,2], [9,6,3] ]Solution
A 90-degree clockwise rotation can be achieved in two steps: transpose the matrix and then reverse every row.Transposing the matrix swaps
matrix[i][j] with matrix[j][i]. This converts rows into columns. After the transpose, reversing every row produces the required 90-degree clockwise rotation.
Both operations can be performed directly on the original matrix, so no additional matrix is required.
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// Transpose the matrix.
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Reverse every row.
for (int i = 0; i < n; i++) {
int left = 0;
int right = n - 1;
while (left < right) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
}
}
Complexity
Every matrix element is processed a constant number of times, resulting inO(nĀ²) time complexity, and only a constant number of variables is used, resulting in O(1) extra space.