Given a mxn matrix, can you rotate it clockwise and counter-clockwise? Can you do it in place?
Analysis
There are two approaches. One way to do it layer by layer. The second approach requires some linear algebra knowledge. Here we'll discuss the second approach - transposing and flipping the matrix.
Transpose
Transpose the matrix first n x m result[x][y] = matrix[y][x] m x n
private int[][] transpose(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] result = new int[n][m];
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
result[x][y] = matrix[y][x];
}
}
return result;
}
Vertical/Horizontal Flip
If rotate clockwise, flip horizontally.
If rotate counterclockwise, flip vertically.
private void horizontalFlip(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
for (int y = 0; y < m; y++) {
for (int x = 0; x < n/2; x++) {
int temp = matrix[y][x];
matrix[y][x] = matrix[y][n - 1 - x];
matrix[y][n - 1- x] = temp;
}
}
}
private void verticalFlip(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m/2; y++) {
int temp = matrix[y][x];
matrix[y][x] = matrix[m - 1 - y][x];
matrix[m - 1 - y][x] = temp;
}
}
}
Rotate Matrix
public int[][] rotateMatrix(int[][] matrix, int flag) {
if (matrix == null || matrix.length == 0)
return matrix;
if (matrix[0] == null || matrix[0].length == 0)
return matrix;
int[][] result;
result = transpose(matrix);
if (flag == 1) // rotate clockwise
horizontalFlip(result);
else // rotate counterclockwise
verticalFlip(result);
return result;
}
Note
Rotation in-place has very limited options in terms of operation. You pretty much have to figure out a way that only uses swapping elements and holding a temp variable. Swapping horizontally, vertically, diagonally, multiple times (with different substrings), etc.
