Facebook Interview Question
Software Engineer / DevelopersWhat an idiot am I! I made A->A' so complicated...
void rotate_matrix_cw_90(int **m, int n)
{
int i, j;
// first mirror the matrix along the diagnal line.
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}
// mirror the matrix horizontally.
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n; j++)
{
int tmp = m[j][i];
m[j][i] = m[j][n - i - 1];
m[j][n - i - 1] = tmp;
}
}
}
Follow below steps:
Step1. take transpose of matrix
Step2. swap columns of transpose of matrix
public class MatrixRotation {
public static void main(String[] arr){
int[][] matrix = new int[6][6];
int i, j, k, temp;
for(i =0; i<6; i++){
for (j=0; j<6; j++)
matrix[i][j] = i*10+j;
}
System.out.println("before transpose");
for(i =0; i<6; i++){
for (j=0; j<6; j++)
System.out.print("\t"+matrix[i][j]);
System.out.println();
}
System.out.println("after transpose");
//Transpose of matrix
for(i =0; i<6; i++){
for (j=i; j<6; j++)
if(i!=j){
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for(i =0; i<6; i++){
for (j=0; j<6; j++)
System.out.print("\t"+matrix[i][j]);
System.out.println();
}
//rotate 90 degree
for(i=0, k =5 ; i < k; i++, k--){
for (j=0; j<6; j++){
//System.out.println("matrix[i][j] = "+ matrix[i][j] + " matrix[k][j] = " + matrix[k][j]);
temp = matrix[j][i];
matrix[j][i] = matrix[j][k] ;
matrix[j][k] = temp ;
}
}
System.out.println("after 90 degree rotation");
for(i =0; i<6; i++){
for (j=0; j<6; j++)
System.out.print("\t"+matrix[i][j]);
System.out.println();
}
}
}
Suppose rotate clockwise 90 degrees, the transformation is of the form (i, j) => (j, N - 1 - i), where N is the number of rows.
Int** RotateMatrix(int** src, int dims) {
Assert.IsNotNull (src);
// init rtv
int** rtv = (int**)malloc(sizeof(int*));
for (int i=0; i<dims; i++) {
rtv[i] = (int*)malloc(dims*sizeof(int));
}
// rtv assignment
for (int row=0; row<dims; row++) {
for(int col=0; col<dims; col++) {
rtv[row][col] = src[col][dims-row];
}
}
return rtv;
}
here is the method to rotate a cartesian point by 90% along z axis, i dont know if that answers your question
multiply (x,y,z) vector with the following matrix
0 -1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
or simply the following
rotate90CCW(x,y,z){
return(-y,x,z);
}
void rotate_matrix_cw_90(int **m, int n)
{
int i, j;
// first mirror the matrix along the diagnal line.
for (i = 0; i < n * 2 -1; i++)
{
int len = (i >= n) ? 2 * n - i - 1 : i + 1;
int start_x = (i >= n) ? i - n + 1 : 0;
int start_y = (i >= n) ? n - 1 : i;
for (j = 0; j < len / 2; j++)
{
int x = start_x + j;
int y = start_y - j;
int tmp = m[y][x];
m[y][x] = m[x][y];
m[x][y] = tmp;
}
}
// mirror the matrix horizontally.
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n; j++)
{
int tmp = m[j][i];
m[j][i] = m[j][n - i - 1];
m[j][n - i - 1] = tmp;
}
}
}
void RotateMatrix(int original[][3], int rows)
{
int start = 0;
int end = rows - 1;
while(end > start)
{
for(int index = start; index < end; index++)
{
int offset = index - start;
int tmp = original[start][index];
original[start][index] = original[end - offset][start];
original[end - offset][start] = original[end][end - offset];
original[end][end - offset] = original[index][end];
original[index][end] = tmp;
}
start++;
end--;
}
}
How about this one guys? For rotation in place.
void RotateInPlace(int n,int** matrix)
{
int jCount =0;
if( n%2 ==0) jCount=n/2;
else jCount = (n/2)+1;
for( int i =0;i< n/2; i++)
{
for( int j=0 ;j < jCount; j++)
{
int starti=i;int loopi=j;int startj=j;int loopj=n-i-1;
int temp = matrix[i][j];
while( !(loopi ==starti && loopj == startj))
{
int temp1= matrix[loopi][loopj] ;
matrix[loopi][loopj] = temp;
temp=temp1;
int t= loopi;
loopi =loopj;
loopj= n-t-1;
}
matrix[loopi][loopj] = temp;
// till we make a circle and reach starting point - keep swapping
}
}
}
#define M 4
#define N 3
int main()
{
int array[M][N];
int t_array[N][M];
int i,j;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
scanf("%d",&array[i][j]);
}
}
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
t_array[j][i] = array[M-i-1][j];
}
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
printf("%d ",t_array[i][j]);
}
printf("\n");
}
return 0;
}
copied from another forum
O(n^2) time and O(1) space algorithm
Rotate by +90:
Transpose
Reverse each row
Rotate by -90:
Transpose
Reverse each column
Rotate by +180:
Method 1: Rotate by +90 twice
Method 2: Reverse each row and then reverse each column
Rotate by -180:
Method 1: Rotate by -90 twice
Method 2: Reverse each column and then reverse each row
Method 3: Reverse by +180 as they are same
Here's the java program to rotate a matrix by 90 degree (clockwise/anticlockwise)
public class Matrix {
static int[][] getMcrossN(int m, int n){
int[][] a = new int[m][n];
int cnt = 1;
for(int i=0; i<m; i++){
for(int j=0;j<n; j++){
System.out.format("%4d",a[i][j]=cnt++);
}
System.out.println();
}
System.out.println("\n\n");
return a;
}
static int[][] rotateMatrix(int[][] x){
int[][] m = new int[x[0].length][x.length];
for(int i=0; i<x[0].length; i++){
for(int j=0; j<x.length; j++){
// System.out.format("%4d",m[i][j]=x[j][x[0].length-1-i]); //rotate by 90 degree anticlockwise.
System.out.format("%4d",m[i][j]=x[x.length-1-j][i]); //rotate by 90 degree clockwise.
}
System.out.println();
}
return m;
}
/**
* @param args
*/
public static void main(String[] args) {
rotateMatrix(getMcrossN(3, 4));
}
}
Here is a solution without using extra space :
public static void rotate(int[][] matrix) {
int N = matrix.length;
for(int i = 0; i < N/2; ++i) {
for(int j = 0; j < (N+1)/2; ++j) {
int temp = matrix[i][j]; // save the top element;
matrix[i][j] = matrix[N-1-j][i]; // right -> top;
matrix[N-1-j][i] = matrix[N-1-i][N-1-j]; // bottom -> right;
matrix[N-1-i][N-1-j] = matrix[j][N-1-i];// left -> bottom;
matrix[j][N-1-i] = temp; // top -> left;
}
}
}
More mentioned here - k2code.blogspot.in/2014/03/rotate-n-n-matrix-by-90-degrees.html
public static void main(String[] args){
int[][] a={
{11,12,13,14},
{21,22,23,24},
{31,32,33,34},
{41,42,43,44}
};
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
System.out.print(a[i][j] +" ,");
}
System.out.println("\r\n");
}
System.out.println("\r\n");
System.out.println("---------------------------------");
rotate(a);
}
static void rotate(int[][] a){
int rowlength=a.length;
int[][] r=new int[rowlength][];
for(int i=0;i<rowlength;i++){
r[i]=new int[a[i].length];
}
for(int j=0;j<a.length;j++){
for(int k=0;k<a[j].length;k++){
r[k][rowlength-j-1]=a[j][k];
}
}
for(int i=0;i<r.length;i++){
for(int j=0;j<r[i].length;j++){
System.out.print(r[i][j] +" ,");
}
System.out.println("\r\n");
}
}
For square matrix
public static void rotate(int[][] matrix) {
int N = matrix.length;
for(int row = 0; row < N/2; row++) {
for(int col = row; col < N - 1- row; col++) {
int tmp1 = matrix[row][col];
int tmp2 = matrix[col][N -1 - row];
int tmp3 = matrix[N -1 - row][N -1 - col];
int tmp4 = matrix[N -1 - col][row];
matrix[row][col] = tmp4;
matrix[col][N -1 - row] = tmp1;
matrix[N -1 - row][N -1 - col] = tmp2;
matrix[N -1 - col][row] = tmp3;
}
}
}
My program works for square matrices -:
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class RotateAnImageBy90Degrees {
// this function is used to rotate the square matrix by 90 degrees
public static void rotateMatrixBy90Degrees(int[][] matrix){
int N = matrix.length;
// first find the transpose of the matrix
for(int i = 0; i < N; ++i){
for(int j = i; j < N; ++j){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// reverse the columns of the matrix till N/2 to rotate the matrix by 90 degrees
for(int i = 0; i < N; ++i){
for(int j = 0; j < N/2; ++j){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][N-j-1];
matrix[i][N-j-1] = temp;
}
}
}
public static void displayMatrix(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.println();
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N;
N = 0;
System.out.println("Enter the dimensions of the square matrix you want : ");
N = Integer.parseInt(br.readLine());
int[][] matrix = new int[N][N];
for(int i = 0; i < N; ++i){
String[] s = br.readLine().split("\\s+");
int[] colValues = new int[s.length];
for(int j = 0; j < colValues.length; ++j)
colValues[j] = Integer.parseInt(s[j]);
for(int j = 0; j < colValues.length; ++j)
matrix[i][j] = colValues[j];
}
System.out.println("The original matrix is as follows -: ");
displayMatrix(matrix);
rotateMatrixBy90Degrees(matrix);
System.out.println("The matrix rotated by 90 degrees is as follows -: ");
displayMatrix(matrix);
}
}
class hello {
public static void main(String[] args) throws java.lang.Exception {
int[] ar = new int[10];
ar[1] = 1;
ar[2] = 2;
ar[3] = 3;
ar[4] = 4;
ar[5] = 5;
ar[6] = 6;
ar[7] = 7;
ar[8] = 8;
ar[9] = 9;
int n = 1;
int m = 0;
System.out.println("The Original Matrix is");
for (int i = 1; i <= 3; i++) {
for (int j = n; j <= (i * 3); j++) {
System.out.print(" " + ar[j]);
System.out.print(" ");
m = n++;
}
n = m + 1;
System.out.println();
}
System.out.println();
System.out.println("After Rotating it to 90 degree");
for (int i = 3; i > 0; i--) {
for (int j = i; j <= 9;) {
System.out.print(" " + ar[j]);
System.out.print(" ");
j = j + 3;
}
System.out.println("");
}
}
}
public static void main(String[] args) throws java.lang.Exception {
int[] ar = new int[10];
ar[1] = 1;
ar[2] = 2;
ar[3] = 3;
ar[4] = 4;
ar[5] = 5;
ar[6] = 6;
ar[7] = 7;
ar[8] = 8;
ar[9] = 9;
int n = 1;
int m = 0;
System.out.println("The Original Matrix is");
for (int i = 1; i <= 3; i++) {
for (int j = n; j <= (i * 3); j++) {
System.out.print(" " + ar[j]);
System.out.print(" ");
m = n++;
}
n = m + 1;
System.out.println();
}
System.out.println();
System.out.println("After Rotating it to 90 degree");
for (int i = 3; i > 0; i--) {
for (int j = i; j <= 9;) {
System.out.print(" " + ar[j]);
System.out.print(" ");
j = j + 3;
}
System.out.println("");
}
}
{
public static void main(String[] args) throws java.lang.Exception {
int[] ar = new int[10];
ar[1] = 1;
ar[2] = 2;
ar[3] = 3;
ar[4] = 4;
ar[5] = 5;
ar[6] = 6;
ar[7] = 7;
ar[8] = 8;
ar[9] = 9;
int n = 1;
int m = 0;
System.out.println("The Original Matrix is");
for (int i = 1; i <= 3; i++) {
for (int j = n; j <= (i * 3); j++) {
System.out.print(" " + ar[j]);
System.out.print(" ");
m = n++;
}
n = m + 1;
System.out.println();
}
System.out.println();
System.out.println("After Rotating it to 90 degree");
for (int i = 3; i > 0; i--) {
for (int j = i; j <= 9;) {
System.out.print(" " + ar[j]);
System.out.print(" ");
j = j + 3;
}
System.out.println("");
}
}
}
Here's my solution with extra space.
package com.learning.java.library;
/**
* Created by ejangpa on 1/12/2017.
*/
public class ArrayRotationLeftBy90Degree {
public static void main(String[] args) {
int[][] arrayA = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int[][] arrayB = new int[3][3];
System.out.println("Initial Array :");
printArray(arrayA);
System.out.println();
System.out.println("Left Rotated Array");
rotateArrayAntiClockwise(arrayA, arrayB);
int[][] arrayC = new int[3][3];
System.out.println("Array Rotated Again :");
rotateArrayAntiClockwise(arrayB, arrayC);
System.out.println("Right Rotated Array");
rotateArrayClockwise(arrayA, arrayB);
}
static void rotateArrayAntiClockwise(int[][] arrayA, int[][] arrayB) {
for(int i = 0; i < arrayA.length; i++) {
for(int j = 0 ; j <arrayA.length; j++) {
int k = i;
int l = (arrayA.length - 1) - j;
arrayB[l][k] = arrayA[i][j];
}
}
printArray(arrayB);
}
static void rotateArrayClockwise(int[][] arrayA, int[][] arrayB) {
for(int i = 0; i < arrayA.length; i++) {
for(int j = 0 ; j <arrayA.length; j++) {
int k = (arrayA.length - 1 ) - i;
int l = j;
arrayB[l][k] = arrayA[i][j];
}
}
printArray(arrayB);
}
static void printArray(int[][] arrayB) {
for(int i = 0; i < arrayB.length; i++) {
for(int j = 0; j < arrayB.length; j++) {
System.out.print(arrayB[i][j] + " ");
}
System.out.println();
}
}
}
package com.mahesh.practice;
import java.util.Scanner;
public class MatrixAntiClock
{
public static void main(String[] args)
{
int i,j,k;
int m[][] = new int[10][10];
Scanner sc=new Scanner(System.in);
System.out.println("enter the size of matrix");
k=sc.nextInt();
{
System.out.println("enter matrix values");
for(i=0;i<k;i++)
{
for(j=0;j<k;j++)
{
m[i][j]=sc.nextInt();
}
}
System.out.println("Matrix is:");
for(i=0;i<k;i++)
{
for(j=0;j<k;j++)
{
System.out.print(m[i][j]);
System.out.print(" ");
}
System.out.println(" ");
}
}
System.out.println("after Anti clocking Matrix is:");
for(j=k-1;j>=0;j--)
{
for(i=0;i<k;i++)
{
System.out.print(m[i][j]);
System.out.print(" ");
}
System.out.println(" ");
}
}
}
Can the matrix be of any form ? If the matrix is square ... the rotation can be done in-place ... however, since one of the requirements is using no extra space .. then rotating matrices that are rectangle in-place is impossible .. since the memory layout then is going to be different .. can the poster please comment on that
- Vir Pratap Uttam May 04, 2015