Given an n x n 2D matrix, rotate it 90 degrees clockwise in-place.
Input: [[1,2,3],[4,5,6],[7,8,9]] → Output: [[7,4,1],[8,5,2],[9,6,3]]Input: [[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]]
Two-step process: (1) Transpose the matrix (swap matrix[i][j] with matrix[j][i]); (2) Reverse each row.
- Transpose: for i from 0 to n-1: for j from i+1 to n-1: swap matrix[i][j] and matrix[j][i].
- Reverse each row: for each row, use two pointers to reverse.
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// Transpose
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++) { int t=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=t; }
// Reverse each row
for (int[] row : matrix) {
int lo=0, hi=row.length-1;
while (lo<hi) { int t=row[lo]; row[lo]=row[hi]; row[hi]=t; lo++; hi--; }
}
}
}
- Time Complexity: O(N^2)
- Space Complexity: O(1)