Amazon Interview Question Software Engineer / Developers
0of 0 votesRotate a n*n (square) matrix by 90 degrees.
Country: United States
Interview Type: In-Person
Take the transpose of the matrix and reverse elements row-wise
class Rotate90 {
public static void reverseElementsRowWise(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n / 2; ++j) {
int temp = matrix[i][n - j - 1];
matrix[i][n - j - 1] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
public static void transpose(int[][] matrix) {
int n = matrix.length;
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;
}
}
}
public static void rotate90(int[][] matrix) {
transpose(matrix);
reverseElementsRowWise(matrix);
}
public static void print(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
System.out.print(matrix[i][j]);
System.out.print(' ');
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
System.out.println("before");
print(matrix);
rotate90(matrix);
System.out.println("after");
print(matrix);
}
}
good solution . could you please explain the concept behind this? To rotate to 180 do we need to rotate to 90 two times?
Thank you :)
The idea is to see how the elements change position. Since this is rotation, the elements have to change in a sane way without jumping around. Looked at it and figured it out.
@nmc : Yes. To rotate the array 180 degrees, call rotate90(matrix) twice.
@swathi: The variable start has been removed.
Cheers.
void rotateSquareMatrixby90(int [][]sa){
for (int i = 0; i < sa.length-1; i++) {
int t = sa[i][sa.length-1];
sa[i][sa.length-1] = sa[0][i];
int t1 = sa[sa.length-1][sa.length-1-i];
sa[sa.length-1][sa.length-1-i] = t;
t = sa[sa.length-1-i][0];
sa[sa.length-1-i][0] = t1;
sa[0][i] = t;
}
}
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
13 9 5 1
14 6 7 2
15 10 11 3
16 12 8 4
Sorry This is wrong :)
static void rotateSquareMatrixby90(int [][]sa){
for (int j = 0; j < (sa.length/2); j++)
for (int i = j; i < sa.length-1-j; i++) {
int t = sa[i][sa.length-1-j];
sa[i][sa.length-1-j] = sa[j][i];
int t1 = sa[sa.length-1-j][sa.length-1-j-(i-j)];
sa[sa.length-1-j][sa.length-1-j-(i-j)] = t;
t = sa[sa.length-1-j-(i-j)][j];
sa[sa.length-1-j-(i-j)][j] = t1;
sa[j][i] = t;
}
}
This might work
package t1;
import java.awt.Point;
public class M3x {
final int n;
int[][] m;
M3x(int n){
this.n =n;
}
void fill(){
m =new int[n][n];
int num = 0;
for (int i=0;i<m.length;i++){
int[] row = m[i];
for (int j = 0; j < row.length; j++) {
row[j]=++num;
}
}
}
void print(){
for (int i=0;i<m.length;i++){
int[] row = m[i];
for (int j = 0; j < row.length; j++) {
System.out.printf("%d\t", row[j]);
}
System.out.println();
}
for (int i=0;i<n;i++)
System.out.print("=======");
System.out.println();
}
void rotate(){
Point p = new Point();
int maxRows = m.length/2 ;
for (int i=0;i<maxRows;i++){
p.y = i;
int[] row = m[i];
for (int j = i; j < row.length-i-1; j++) {
p.x = j;
int v= m[p.y][p.x];
for (;;){
rotatePoint(p);
int cur = m[p.y][p.x];
m[p.y][p.x] = v;
if (p.y==i && p.x==j)
break;
v =cur;
}
}
}
}
void rotatePoint(Point p){
int x = n-p.y - 1;
int y = p.x;
p.x = x;
p.y = y;
}
public static void main(String[] args) {
M3x m3x =new M3x(9);
m3x.fill();
m3x.print();
m3x.rotate();
m3x.print();
}
}
Following method will give the required rotational functionality.
private static int[][] rotateMatrix(int[][] matrix) {
int[][] rotatedMatrix = new int[matrix.length][matrix.length];
int len = matrix.length - 1;
for (int i = 0; i <= len; i++) {
for (int j = 0; j <= len; j++) {
rotatedMatrix[j][len - i] = matrix[i][j];
}
}
return rotatedMatrix;
}
AnanthaNag KUNDANALA
Following is the full class implementation ...
public class Main {
public static void main(String argc[]) {
int matrix[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12},{13,14,15,16}};
int[][] newMatrix = rotateMatrix(matrix);
display(newMatrix);
}
private static int[][] rotateMatrix(int[][] matrix) {
int[][] rotatedMatrix = new int[matrix.length][matrix.length];
int len = matrix.length - 1;
for (int i = 0; i <= len; i++) {
for (int j = 0; j <= len; j++) {
rotatedMatrix[j][len - i] = matrix[i][j];
}
}
return rotatedMatrix;
}
private static void display(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println("");
}
}
}
AnanthaNag KUNDANALA
requires extra n*n memory though. the question doesn't say 'in-place' but probably it'd be looked upon.
- Vir Pratap Uttam May 04, 2015private static int[][] rotateMatrixBy90Degree(int[][] matrix, int n) { for (int layer = 0; layer < n / 2; layer++) { int first = layer; int last = n - 1 - layer; for (int i = first; i < last; i++) { int offset = i - first; int top = matrix[first][i]; matrix[first][i] = matrix[last - offset][first]; matrix[last - offset][first] = matrix[last][last - offset]; matrix[last - offset][last] = matrix[i][last]; matrix[i][last] = top; } } System.out.println("Matrix After Rotating 90 degree:-"); printMatrix(matrix, n); return matrix; }