Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
private 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;
}
there is small problem in for inner loop in place of
"matrix[last - offset][last] = matrix[i][last];"
it should be
matrix[last][last-offset] = matrix[i][last];
// If we rotate the Matrix of nxm by 90* then it will become matrix of mxn
// We will have to create a new 2-D array , like this rot_arr [row][col]
void rotate(int row int col, int arr[][row],int rot_arr[][col])
{
for(int j = 1; j < row; j++)
{
for (int i = m-1 , k = 0; i >= 0, k < m; i--, k++)
{
arr_rot[j][k] = arr[j][i];
}
}
}
// optimzing on that, no extra memory .
void rotate(vector< vector<int> >& a, int n)
{
for (cn=n, i=0; cn>=2 ; cn-=2; i++)
{
int j = cn-1;
for (step=0; step < cn-1; step++)
{
rotate_ele(a[i][i+step], a[i+step][j], a[i+cn-1][j-step], a[i+cn-1-step][i]);
}
}
}
void rotate_ele(int &a, int& b, int& c, int& d)
{
int temp = a;
a = d;
d = c;
c = b;
b = temp;
}
Is this answer right?
public void rotateMN(int[][] input){
int i = input.length;
int j = input[0].length;
int m = j;
int n = i;
int[][] newArray = new int[m][n];
for(int j = input[0].length-1, m=0; ;i--, m++ ){
for(int i = input.length-1, n=0; i >= 0 ; i--, n++){
newArray[m][n] = input[i][j];
}
}
}
Will this also work for N*N matrix rotation by 90 degrees?
The time complexity is O(N) since it just traverse the input matrix and copy it to the new matrix. The space complexity is (MN) + (MN) = So MN.
Is it possible to do rotation for M * N matrix in space? If so please provide that answer
Whats this space and time complexity?
#include<iostream>
using namespace std;
class Matrix{
int *mat;
int row,column;
public:
void readMatrix();
void rotateMatrix90DegClockWise();
void transposeMatrix();
void displayMatrix();
void interchangeColumns();
};
void Matrix::readMatrix(){
cout<<"Enter the row size : ";
cin>>row;
cout<<"Enter the column size : ";
cin>>column;
mat = new int[row*column];
for(int i = 0;i<row ;i++){
cout<<"Enter the elements of row "<<i+1<<" : ";
for(int j=0;j<column;j++)
cin>>*(mat+i*column+j);
}
}
void Matrix::displayMatrix(){
for(int i = 0;i<row ;i++){
cout<<endl;
for(int j=0;j<column;j++)
cout<<*(mat+i*column+j)<<" ";
}
}
void Matrix::transposeMatrix(){
int *trans = new int(row*column);
for(int i=0;i<row*column;i++){
*(trans+i) = 0;
}
for (int i = 0; i < row; i++){
for (int j = 0; j < column; j++){
*(trans +j*row +i) = *(mat + i*column +j);
}
}
row = row + column;
column = row - column;
row = row - column;
for(int i=0;i<row*column;i++){
*(mat+i) = *(trans+i);
}
}
void Matrix::interchangeColumns(){
int temp = 0;
for(int i=0;i<row;i++){
for(int j=0;j<column/2;j++){
temp = *(mat+i*column+j);
*(mat+i*column+j) = *(mat+column*i+(column-1-j));
*(mat+column*i+(column-1-j)) = temp;
}
}
}
void Matrix::rotateMatrix90DegClockWise(){
transposeMatrix();
interchangeColumns();
}
int main(){
Matrix mat1;
mat1.readMatrix();
cout<<"\n Original Matrix ";
mat1.displayMatrix();
mat1.rotateMatrix90DegClockWise();
cout<<"\n Rotated Matrix ";
mat1.displayMatrix();
}
#include <stdio.h>
#include <stdlib.h>
#define M 6
#define N 7
int Arr[M*N];
int main(){
int i,k;
for(i =0; i <M*N ; i ++)
{
Arr[i] = rand()%100;
}
printf("\n ----- \n");
for(i =0; i <M*N ; i ++)
{
printf("%d\t", Arr[i]);
if( (i+1) % M == 0 )
printf("\n");
}
printf("\n ----- \n");
for(i =0; i <M*N ; i ++)
{
k = ((i*M)+M-1) % (M*N+1);
printf("%d\t", Arr[k]);
if( (i+1) % N == 0 )
printf("\n");
}
printf("\n ----- \n");
}
Below is the efficient code of doing it,
Time : O(n2)
Space: O(1) Inplace.
complete implementation and logic can be found at : ms-amazon.blogspot.in/2013/05/rotate-matrix-90-degrees-clockwise.html
void setNewIndex(int &row, int &col, int N)
{
int temp = col;
col = N - 1 - row;
row = temp;
}
void moveCyclic(int row , int col , int N)
{
int temp1 = matrix[row][col];
int temp2;
for(int k=1; k<=4; k++)
{
setNewIndex(row,col, N);
temp2 = matrix[row][col];
matrix[row][col] = temp1;
temp1 = temp2;
}
}
You cannot rotate a MxN matrix in-place.
MxN matrix means M - rows and N - columns and on rotating it by 90deg, rows change to columns and columns to rows i.e. M-columns and N-rows which calls for allocating new matrix of size NxM in memory.
1 2 3 4 5
6 7 8 9 10
when rotated 90deg clockwise forms.
6 1
7 2
8 3
9 4
10 5
Please let me know if have not understood the question properly.
People down vote without even understanding the post, bad.
can anyone write a code for inplace 90deg rotation of MXN matrix?
If some can, I am more than happy to accept the downvote.
Rotating a MxN array is trivial if you have extra O(NM) memory.
simply copy contents of current cell to new cell.
RotatedA[col][M-1-row] = A[row][col]
Traverse input array and just copy content of current cell to new cell, O(NM) solution I don't understand the difficulty part here.
Depending on how you represent your matrices, you can do rotations in O(1) time with O(1) additional space. Further, matrices that you have rotated (and transformed in other ways) can share a single underlying element array with the original. The idea is to think of rotating a matrix not as a rearrangement of elements but as a transformation of coordinates, which can be done in constant time. I give a sample implementation (in Python) in my practice repo on GitHub:
github.com/tmoertel/practice/blob/master/careercup/rot_matrix_90.py
Cheers,
Tom
// no extra memory and less # of swaps compared to other method
void rotate(vector< vector<int> >& a, int n)
{
for (cn=n, i=0; cn>=2 ; cn-=2; i++)
{
int j = cn-1;
for (step=0; step < cn-1; step++)
{
rotate_ele(a[i][i+step], a[i+step][j], a[i+cn-1][j-step], a[i+cn-1-step][i]);
}
}
}
void rotate_ele(int &a, int& b, int& c, int& d)
{
int temp = a;
a = d;
d = c;
c = b;
b = temp;
}
If your Matrix is Square Matrix then follow this answer
public static void rotateArray(int arr[][], int N) {
int layer = 0;
while(layer < N/2) {
int low = layer;
int high = N - 1 - layer;
for(int i = low; i < high; i++) {
int t = arr[low][i];
arr[low][i] = arr[i][high];
arr[i][high] = arr[high][N-i-1];
arr[high][N-i-1] = arr[N-i-1][low];
arr[N-i-1][low] = t;
}
layer++;
}
}
#include<stdio.h>
void rotate(int *a,int *b,int *c,int *d) {
int t1 = *b;
*b = *a;
int t2 = *d;
*d = t1;
*a = *c;
*c = t2;
}
print(int n,int a[][n]) {
int i,j;
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
printf(" %2d " , a[i][j] );
}
printf("\n");
}
}
void main(){
const int n = 4;
int ar[4][4]={ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16};
print(n,ar);
int layer, noOfLayers = n / 2 ;
for( layer = 0 ; layer < noOfLayers ; layer++ ) {
int a1 = layer , a2 = layer ;
int b1 = layer , b2 = n - 1 - layer;
int c1 = n - 1 - layer , c2= layer ;
int d1 = n - 1 - layer , d2 = n - 1 - layer ;
int i;
for ( i = layer ; i < n - 1 - layer ; i++ ) {
int* a = &ar[a1][a2+i];
int* b = &ar[b1+i][b2];
int* c = &ar[c1-i][c2];
int* d = &ar[d1][d2-i];
printf("%2d %2d %2d %2d \n",*a,*b,*c,*d);
rotate(a,b,c,d);
}
}
printf("\n-------------------\n");
print(n,ar);
getch();
}
Hey I have written in C language:
#include<stdio.h>
void rotate(int *a,int *b,int *c,int *d) {
int t1 = *b;
*b = *a;
int t2 = *d;
*d = t1;
*a = *c;
*c = t2;
}
print(int n,int a[][n]) {
int i,j;
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
printf(" %2d " , a[i][j] );
}
printf("\n");
}
}
void main(){
const int n = 4;
int ar[4][4]={ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16};
print(n,ar);
int layer, noOfLayers = n / 2 ;
for( layer = 0 ; layer < noOfLayers ; layer++ ) {
int a1 = layer , a2 = layer ;
int b1 = layer , b2 = n - 1 - layer;
int c1 = n - 1 - layer , c2= layer ;
int d1 = n - 1 - layer , d2 = n - 1 - layer ;
int i;
for ( i = layer ; i < n - 1 - layer ; i++ ) {
int* a = &ar[a1][a2+i];
int* b = &ar[b1+i][b2];
int* c = &ar[c1-i][c2];
int* d = &ar[d1][d2-i];
printf("%2d %2d %2d %2d \n",*a,*b,*c,*d);
rotate(a,b,c,d);
}
}
printf("\n-------------------\n");
print(n,ar);
getch();
}
for(int i=0;i<ar.length;i++)
{
for(int j=0;j<ar.length;j++)
{
if(i<ar.length/2&&j<ar.length/2)
{
int temp=ar[i][j];
ar[i][j]=ar[ar.length-1-i][j];
ar[ar.length-1-i][j]=ar[ar.length-1-i][ar.length-1-j];
ar[ar.length-1-i][ar.length-1-j]=ar[i][ar.length-j-1];
ar[i][ar.length-j-1]=temp;
}
}
}
for(int i=0;i<ar.length;i++)
{
for(int j=0;j<ar.length;j++)
{
if(i<ar.length/2&&j<ar.length/2)
{
int temp=ar[i][j];
ar[i][j]=ar[ar.length-1-i][j];
ar[ar.length-1-i][j]=ar[ar.length-1-i][ar.length-1-j];
ar[ar.length-1-i][ar.length-1-j]=ar[i][ar.length-j-1];
ar[i][ar.length-j-1]=temp;
}
}
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int x, y;
int matriks[105][105];
cin>>x>>y;
for(int i=1; i<=x; i++){
for(int j=1; j<=y; j++){
cin>>matriks[i][j];
}
}
for(int i=1; i<=y; i++){
for(int j=x; j>0; j--){
cout<<matriks[j][i];
if(j>1){
cout<<" ";
}
else cout<<endl;
}
}
return 0;
}
rotate( int *p, int M, int N){
for (i=0; i < M*N; i ++) {
k = ( (i*M)+M-1) % ((M*N)+1) ;
printf("%d ", p[k]) ;
if( i % M == 0)
printf("\n");
}
The index into the array(i) is converted into another index into the new array (k)
using a mapping.
90 degree clockwise rotation of n*m array means
row i of input array should copy to column n-1-i output array
and column j of input array should copy to row j of output array
- ehsan October 03, 2013int [][] rotate(int [][] input){ int n =input.length(); int m = input[0].length(); int [][] output = new int [m][n]; for (int i=0; i<n; i++) for (int j=0;j<m; j++) output [j][n-1-i] = input[i][j]; return output; }