Amazon Interview Question
Country: United States
Assuming a (n x n ) matrix
This is simple solution but not necessarily intuitive ...
The steps are for a clockwise rotation:
1. Transpose the matrix
2. Swap column i with column (n-i)
Reason - When you rotate a matrix (let's say clockwise) you are moving the first row to last column , second row to second last column and likewise
and when you transpose a matrix , you are moving the first row to first column , second to second and likewise
so all you have to do after transposing the matrix is just swap the first column with last and second with second last and so on
Time Complexity - O(n2)
First of all the Matrix has to be nxn (square) M[n][n]
This can be done in a simpler repetition of the step for outermost to innermost ring (n/2 rings)
Last_Row = n -1;
Last_Column = n -1;
First_Row = 0;
First_Column = 0;
while (Last_Row > FirstRow){
FOR(j = First_column; i <= Last_Column; j++){ // can use row or column
temp = M[Last_Row][j];
M[Last_Row][j] = M[j][Last_Column];
M[j][Last_column] = M[First_Row][j];
M[First_Row][j] = M[j][First_column];
M[j][First_column] = temp;
} // end ring iteration
// move to inner ring
First_Row++;
First_column++;
Last_Row --;
Last_column--;
} // end radial iteration
int a[5][5] = { {1,2,3,4,5}, {6,7,8,9,10}, {11,12,13,14,15}, {16,17,18,19,20}, {21,22,23,24,25} };
int n = 5;
for(int i=0; i<n/2; i++) {
for(int j=0; j<(n+1)/2; j++) {
int temp = a[i][j];
a[i][j] = a[n-1-j][i];
a[n-1-j][i] = a[n-1-i][n-1-j];
a[n-1-i][n-1-j] = a[j][n-1-i];
a[j][n-1-i] = temp;
}
}
These solutions here are way out of whack. You only need a simple nested loop to flip the matrix. I am using 3x3 matrix here.
public class FlipMatrix {
public static void main(String[] args) {
int [][] matrix = new int [3][3];
int start = 23;
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j++) {
matrix[i][j] = start++;
}
}
printMatrix(matrix);
// flip
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix [j][i];
matrix [j][i] = temp;
}
}
System.out.println("\n\n");
printMatrix(matrix);
}
static void printMatrix(int [][] matrix) {
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println("");
}
}
}
- Vir Pratap Uttam May 04, 2015