# Matrix Layer Rotation

# Matrix Layer Rotation

Morihei + 4 comments After solving this problem we are set up to go to Las Vegas to empty their roulette tables. We just need to be fast enough to calculate RPM's of roulette ))

nikhilksingh97 + 0 comments lol

foxcrocode + 1 comment I get terrified whenever I see this problem. I end up thinking about Vegas.. it kinda helps me.

shubhamitankr + 0 comments LMAO

*_*

tolgahanalbayrak + 0 comments [deleted]NAklecha + 0 comments # All Solutions Below:

Check out

**SOLUTIONS**to**ALL**implementation questions: https://github.com/Naklecha/hackerrank-algo-implementation*"Make sure you try the question before checking it's solution. Stay Faithful! Happy Coding!"*### PLEASE

*"STAR"*MY REPOSITORY IF YOU LIKE MY WORK :)

Visharad_05 + 5 comments Finally Done !!

Almost sucked all my blood out over it

Nice question :)

kanha001 + 5 comments its not so difficult you need to break down the problem into parts.

Mohinem + 3 comments Yeah.... its as easy as counting the number of downvotes in this comment.

giaym + 0 comments holy crap, had to double take, and it isnt difficult as he said lol

gangaj + 0 comments :D Burn!!

surajvermav38 + 0 comments Nailed it bro!!:p

rchavez + 0 comments [deleted]xayuzaii + 3 comments hi, Im having hard time breaking through developing my logic skills, is there any book or documentation you recommend to read about?

thanks in advance !

priyank_p6492 + 0 comments Work through easier problems first and then come back for the difficult ones like this one is

kaosreigns + 1 comment No amount of documentation can prepare you for a question like this. You have to develop your own algorithm and optimize it. I used a rather unwelcome technique of first brute-forcing my way around the problem and then working on the timeouts. Inefficient but that is how I do it :)

bill_rumbley + 0 comments I'll look at the input constraints then decide if brute force will do it. For example 10^9 rotations suggests I'd better use modulo arithmetic. If there's a mathematical way to solve a problem, it will be much faster than consuming clock cycles in nested iterations. For me, the key to this one was finding a mapping from 'polar' to 'mercator' coordinates, because you are spinning rings of numbers around the matrix.

lausanne_man + 0 comments The solution presented is the brute force algorithm that will time out for large matrices. Maybe I'm reading it wrong?

saulobr88 + 0 comments Thanks for the tip, it has helped me

yerzhik + 2 comments Agree with @kanha001, I dont understand why people downvote him so much. Its breaking the matrix into outer circles and dealing with them separately.

peterkirby + 1 comment I agree. It's a matter of identifying the basic idea (map coordinates to a position in a loop, add to that position and use modulus, compute new coordinates) and then working out any little bugs or off-by-one errors (with a debugger or copious debug printing). It's neither very easy nor very hard.

aayush_break + 0 comments i agree as well ...the tricky part is to extract the layers of the matrix and with each layer we can do left rotation of the array. I hope i am going the right way.

digitizedx + 0 comments True. It is not a hard problem. I am an average guy. I found many easy/medium questions much harder than this one.

tolgahanalbayrak + 0 comments [deleted]

etayluz + 7 comments C Solution:

`int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int rows,cols,rot; scanf("%d%d%d",&rows,&cols,&rot); int arr[rows][cols]; int result[rows][cols]; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { scanf("%d", &arr[r][c]); } } rows--; cols--; for (int r = 0; r <= rows; r++) { for (int c = 0; c <= cols; c++) { int x = r < rows - r ? r : rows - r; int y = c < cols - c ? c : cols - c; int min = x < y ? x : y; int maxRow = rows - min; int maxCol = cols - min; int parameter = (maxRow + maxCol) * 2 - min * 4; int row = r; int col = c; for (int a = 0; a < rot%parameter; a++) { if (col == min && row < maxRow) { row++; } else if (row == maxRow && col < maxCol) { col++; } else if (row > min && col == maxCol) { row--; } else if (row == min && col > min) { col--; } } result[row][col] = arr[r][c]; } } for (int r = 0; r <= rows; r++) { for (int c = 0; c <= cols; c++) { printf("%d ", result[r][c]); } printf("\n"); } return 0; }`

jmzcray + 3 comments What's the logic behind:

`int x = r < rows - r ? r : rows - r; int y = c < cols - c ? c : cols - c;`

?

kaosreigns + 1 comment I may be wrong, but I think he means to check whether he reached the mid-index of the row/column in question. That could explain the "r < rows-r", which would translate to "2r < rows" or "r< (rows/2) ".

ngocminh_oss + 0 comments `r < rows - r ? r : rows - r`

is simply`min(r, rows - r)`

.

hackest + 0 comments It's how he figures out which layer he is on. You only want to operate on a single layer at a time. If you were to min the values of the two operations and print it out in the matrix, you would get 0s on the outside, 1s inside of that, then 2s, etc.

e.g.:

0 0 0 0 0 0 0 1 1 1 1 0 0 1 2 2 1 0 0 1 2 2 1 0 0 1 1 1 1 0 0 0 0 0 0 0

durgaprasadgatt1 + 0 comments variable min is the layer number of the matrix.. to find that we have to do the above calculation.

gabrielsecco22 + 0 comments very elegant way to separate all positions by movements(↑→↓←) and even better way to separete the matrix in these 4 regions.

maximshen + 0 comments pretty amazing. thx

asapper1 + 0 comments Good solution.

You don't even have to initially store all the values in an array. Store the values in your "result" array as you read them. Small fix. Instead of doing

result[row][col] = arr[r][c]

you can just do this

scanf("%d", &result[row][col]);

and avoid having to store all the values twice.

bala1297 + 0 comments brother pls explain me logic

gnakum7845 + 0 comments can you please explain this? i am new to coding..

codezilla1 + 1 comment I am not able to get the logic of this statement:

int parameter = (maxRow + maxCol) * 2 - min * 4;

Can anyone explain please?

miroslavkovar + 0 comments It's simply number of elements of the layer one is currently on;

`maxRow`

and`maxCol`

correspond to coordinates of the "most distant" corner, but you have discount the elements of already shifted layers.

alphaHaxor + 2 comments this question is actually really easy if you use a linear queue to store the values and then just shift and reinsert into the matrix. then recursivly do the same with each layer in the matrix. i dont know why its marked as difficult, but hey free points lol.

_aditi + 2 comments how exactly??i mean, queue will contain the elements in an order .so, how can we shift the elements for different layers in the same queue..?

alphaHaxor + 1 comment use different queue for each layer. i dont think you can shift all elements in the matrixin one queue lol. my solution looks like this, it probably isnt the most efficient but it passed all cases.

`static int[][] matrix; static int R; static int layer; public static void Rotate(int h, int w){ //width and height Queue<Integer> temp = new LinkedList<Integer>(); //shifting and replacing back into real matrix for(int i = 0+layer; i < w-1-layer; i++){ temp.add(matrix[0+layer][i]); } for(int i = 0+layer; i < h-1-layer; i++){ temp.add(matrix[i][w-1-layer]); } for(int i = w-1-layer; i > 0+layer; i--){ temp.add(matrix[h-1-layer][i]); } for(int i = h-1-layer; i > 0+layer; i--){ temp.add(matrix[i][0+layer]); } int redo = R; if((2*(h-layer*2) + 2*(w-layer*2) - 4) > 0){ redo = R%(2*(h-layer*2) + 2*(w-layer*2) - 4); } //doing the shifting int t; for(int i = 0; i < redo; i++){ t = temp.poll(); temp.add(t); } //putting black into matrix for(int i = 0+layer; i < w-1-layer; i++){ //putting queue contents back into the matrix matrix[0+layer][i] = temp.poll(); } for(int i = 0+layer; i < h-1-layer; i++){ matrix[i][w-1-layer] = temp.poll(); } for(int i = w-1-layer; i > 0+layer; i--){ matrix[h-1-layer][i] = temp.poll(); } for(int i = h-1-layer; i > 0+layer; i--){ matrix[i][0+layer] = temp.poll(); } //inner layers if(layer < w/2-1 && layer < h/2-1){ //if there are more layers to be rotated, recursive call layer++; Rotate(h,w); } } public static void main(String[] args) { layer = 0; Scanner sc = new Scanner(System.in); int M = sc.nextInt(); int N = sc.nextInt(); R = sc.nextInt(); sc.nextLine(); matrix = new int[M][N]; for(int y = 0; y < M; y++){ for(int x = 0; x < N; x++){ matrix[y][x] = sc.nextInt(); } if(y == M-1) break; sc.nextLine(); } Rotate(M,N); printMatrix(M,N); } public static void printMatrix(int h, int w){ for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ System.out.print(matrix[y][x]+" "); } System.out.println(); } System.out.println(); }`

aliasliem + 0 comments You're brilliant.

alphaHaxor + 0 comments [deleted]

shamim_hafiz + 2 comments Could the rotation be done inplace? Using a queue will reduce the extra space from M*N to 2(M+N), but can we do it assinging constant auxilary memory?

alphaHaxor + 0 comments looking back at this from a year ago, the code looks terrible lmfao. probably tons of more efficient ways to do this. I just remember using a queue cuz it was easy to copy paste.

mathieu_neron_i1 + 0 comments I was able to do exactly this in my case. I did it by computing the amount of rotations needed for each layers, and swapping each elements accordingly until I reach the end of my number of rotation required. an extra check I had to do was to reinitialize my starting position if we reached our initial position for one of our swap i.e. (0,0) for the first layer.

Here's my code, kinda crappy but it passes all tests:

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static void matrixRotation(int[][] matrix, int m, int n, int r) { int layers = Math.min(m, n)/2; for(int l = 0; l < layers; l++) { int m_l = l+m-2*l; int n_l = l+n-2*l; int nbRotationsNeeded = (m_l-1-l)*2 + (n_l-1-l)*2; int boundedR = r % nbRotationsNeeded; if (boundedR == 0) continue; int rotationCount = 0; int i = l; int j = l; int current_first_i = i; int current_first_j = j; int current = matrix[i][j]; while (rotationCount < nbRotationsNeeded) { int currentRotation = boundedR; while (currentRotation != 0) { // go down if (j == l && i<m_l-1) { i++; } // go right else if (i == m_l-1 && j<n_l-1) { j++; } // go up else if (j == n_l-1 && i>l) { i--; } // go left else if (i == l && j>l) { j--; } currentRotation--; } int temp = matrix[i][j]; matrix[i][j] = current; if (current_first_i == i && current_first_j == j) { // go down if (j == l && i<m_l-1) { i++; } // go right else if (i == m_l-1 && j<n_l-1) { j++; } // go up else if (j == n_l-1 && i>l) { i--; } // go left else if (i == l && j>l) { j--; } current_first_i = i; current_first_j = j; temp = matrix[i][j]; } current = temp; rotationCount++; } } // print for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ System.out.print(matrix[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); int r = in.nextInt(); int[][] matrix = new int[m][n]; for(int matrix_i = 0; matrix_i < m; matrix_i++){ for(int matrix_j = 0; matrix_j < n; matrix_j++){ matrix[matrix_i][matrix_j] = in.nextInt(); } } matrixRotation(matrix, m, n, r); in.close(); } }

pulikutti + 1 comment test case 7, 8 and 9 are failing due to timeout error.. can you pls help

giaym + 1 comment your code is quite short so without reading I guess you are doign a naive approach. To speed up stuff like this you have to precompile metadata and work on it instead of every individual value. So think how you can rotate a matrix without rotating each element step by step their positions one by one.

As a second hint write a function: GetValueOfRotatedPosition(int i, int j, matrix m, int r) that will return the value of m[i][j] rotated by r in O(1) or as close as possible. Any heavy computation has to be done beforehand to build up the metadata so this function can execute quick.

abhijeetagnihot1 + 0 comments [deleted]

ledmirage + 13 comments just sharing my solution, passed all testcases with 0 or 0.01s on first submisson.

my approach is to construct a linear array (insted of handlling a 2d array) from each layer of the matrix, once you have the linear array, rotating it is easy by just finding the new starting position and fill the original matrix layer again starting from that position.void dorotate (long r, long **matrix, int m, int n) { int k=m; long *flatten; if (n<m) k=n; flatten = malloc ( (m*2+(n-2)*2) * sizeof (long) ); for (int i=0; i<k; i++) { if ((i+1)*2 > k) break; int ptr=0; //top row, left to right for (int j=i; j<n-i; j++) { flatten[ptr++] = matrix[i][j]; } // right column, top to bottom for (int j=i+1; j<m-i; j++) { flatten[ptr++] = matrix[j][n-1-i]; } // bottom row, right to left for (int j=n-2-i; j>=i; j--) { flatten[ptr++] = matrix[m-1-i][j]; } // left column, bottom to top for (int j=m-2-i; j>i; j--) { flatten[ptr++] = matrix[j][i]; } //printf ("%d - ", ptr); //for (int p=0; p<ptr; p++) { //printf ("%ld ", flatten[p]); //} //printf ("\n\n"); int new_start_pos = r%ptr; //printf ("new_start_pos = %d ", new_start_pos); //printf ("\n\n"); if (new_start_pos>0) { //top row, left to right for (int j=i; j<n-i; j++) { matrix[i][j] = flatten[new_start_pos]; new_start_pos = (new_start_pos+1) % ptr; } // right column, top to bottom for (int j=i+1; j<m-i; j++) { matrix[j][n-1-i] = flatten[new_start_pos]; new_start_pos = (new_start_pos+1) % ptr; } // bottom row, right to left for (int j=n-2-i; j>=i; j--) { matrix[m-1-i][j] = flatten[new_start_pos]; new_start_pos = (new_start_pos+1) % ptr; } // left column, bottom to top for (int j=m-2-i; j>i; j--) { matrix[j][i] = flatten[new_start_pos]; new_start_pos = (new_start_pos+1) % ptr; } } //display_matrix (matrix, m, n); //printf ("\n\n"); } if (!flatten) free(flatten); }

thehuehueking + 0 comments holy moly, never thought about the problem like this :/

avinashshenoy97 + 1 comment I used a similar approach by making a linear array for each layer and then finding the new starting position and creating the new matrix from it. It still timed out out on cases 3, 4, 7, 8. :(

ledmirage + 1 comment how did u find the new position? for my case i just simply do a modular operation:

`int new_start_pos = r%ptr;`

if you actually do actual N rotations (on the linear array) then I think it will still take long time.

avinashshenoy97 + 3 comments This is the code I used.

`for(i = 0 ; i < mi ; i++) { l = 2*((r-2*i) + (c-2*i)) - 4; rota = rot; while( rota >= l ) rota -= l; for(j = rota, k = 0 ; k < l ; j++, k++) { rs1[i][k] = rs[i][j]; if( j == (l-1) ) j = -1; } }`

If the matrix is to be rotated by l times, where l is the length of the layer in question, then essentially no rotation is necessary since every element is in it's initial position at the end of all the rotations.

So rot is the variable that stores the rotations by input. "rota" is just a temporary variable and it is repeatetively subtracted by l. Then the new array is filled from the new starting position which is "rota" as after n rotations, the nth element in the linear array should be the first.

The only thing is that I fill another linear array first and then make the matrix from it. Do you think I should just skip this and directly make the array matrix?

EDIT : Okay nevermind. I tried skipping using the second linear array. Still timed out.

sharmasim319 + 1 comment can you please explain the use of bottom for loop

avinashshenoy97 + 0 comments Sure!

My program basically converts each ring of the matrix into a linear array. Once this linear array is constructed, if the number of rotations is "n" then I start from the nth index of the linear array and I copy it to another linear array (rs1 in my program).

That is what the bottom for loop is for!

I thought it would make it easier to copy it back into a matrix but it was timing out.

manjiri + 0 comments Can you please suggest what may be wrong in my code . only a few test cases are being staisfied. in rest ofthe cases i am getting wrong answers and not timeout . int main() {

`/* Enter your code here. Read input from STDIN. Print output to STDOUT */ long long int a[300][300],temp[1300],temp2[1300],r; int rowstart,rowend,colstart,colend,modulus,k,m,row,col,l,n,i,j; scanf("%d %d %lli",&m,&n ,&r); for(i=0 ; i<m ; i++) { for(j=0 ; j<n ; j++) { scanf("%lli",&a[i][j]); } } colstart = 0; colend = n-1; for(rowstart=0,rowend=m-1; rowstart<rowend; rowstart++,rowend--) { k=0; modulus = (rowend-rowstart + 1)*2 + (colend-colstart + 1)*2-4; r= r%modulus; if(r != 0) { for(row = rowstart ; row<=rowend; row++) { temp[k++] = a[row][colstart]; } for(col = colstart+1 ; col<colend ; col++) { temp[k++] = a[rowend][col]; } for(row = rowend ; row >= rowstart ; row--) { temp[k++] = a[row][colend]; } for(col = colend-1; col>colstart ; col--) { temp[k++] = a[rowstart][col]; } for(l=0 ; l<k ; l++) { temp2[(l%k+r%k)%k] = temp[l]; } k=0; for(row = rowstart ; row<=rowend; row++) { a[row][colstart] = temp2[k]; k++; } for(col = colstart+1 ; col<colend ; col++) { a[rowend][col] = temp2[k]; k++; } for(row = rowend ; row >= rowstart ; row--) { a[row][colend] = temp2[k]; k++; } for(col = colend-1; col>colstart ; col--) { a[rowstart][col] = temp2[k]; k++; } colstart++; colend--; } } for(i=0 ; i<m ; i++) { for(j=0 ; j<n ; j++) { printf("%lli ",a[i][j]); } printf("\n"); } return 0;`

}

RogerB + 0 comments This is your culprit:

`while( rota >= l ) rota -= l;`

From the problem description, rota can be as high as 1,000,000,000. On the innermost ring, l can be as small as 4. This could lead to that one innocuous-looking loop running up to 250,000,000 times on a given ring. Try replacing that loop with something like this:

`rota = rota % l;`

coolcoder001 + 2 comments hi , pardon my ignorance , what is the reason behind doing "(m*2+(n-2)*2)".. how did you come up this ? can u plz advice ?

helio_clementino + 0 comments I used this formula too : 2*currentM + 2*(currentN-2); It computes how many elements do you have when considering just the elements on the borders. For example, a 4 X 4 matrix have 12 elements on the outermost borders : 4 on the top (first line), 4 on the bottom (last line) and 2 on each side (excluding the corner elements already summed up on the top and bottom).

r_wandarosanza + 0 comments or you can also using (m*n-(m-2)*(n-2))

avinashshenoy97 + 0 comments This approach didn't work for me. :(

Test cases #3 #4 #7 #8 timed out.

persoy + 0 comments This is great solution. Bravo !!!

madbrain + 0 comments Great minds think alike :)

I used pretty much the same solution.

I have no idea why this problem is rated "difficult" and worth 80 points. I got this one one the first try and passed all the test cases with the first submission in near-0 time. Some of the problems rated "easy" or "medium" took me much longer.

bismarc + 0 comments Hello, I practised the same mechanism as you did above and my sample test cases are passed but getting wrong answer for test cases once i submit it. Please help.

void matrix_rotation(long *input, long r) {

`int start_i=0, count; int start_j=0; int row=max_row; int column=max_column; int size=2*row+2*(column-2); while(start_i<max_row/2 && start_j<max_column/2) { r=r%size; count=0; long arr[size]; for(int j=start_j; j<column; j++) arr[count++]=input[start_i*max_column+j]; for(int i=start_i+1; i<row; i++) arr[count++]=input[i*max_column+column-1]; for(int j=column-2; j>start_i-1; j--) arr[count++]=input[(row-1)*max_column+j]; for(int i=row-2; i>start_i; i--) arr[count++]=input[i*max_column+start_j]; //copying back to main input count=r; for(int j=start_j; j<column; j++) { count=count%size; input[start_i*max_column+j]=arr[count++]; } for(int i=start_i+1; i<row; i++) { count=count%size; input[i*max_column+column-1]=arr[count++]; } for(int j=column-2; j>start_i-1; j--) { count=count%size; input[(row-1)*max_column+j]=arr[count++]; } for(int i=row-2; i>start_i; i--) { count=count%size; input[i*max_column+start_j]=arr[count++]; } start_i++; start_j++; row--; column--; size=2*(row-1)+2*(column-3); }`

}

bhai_gajab + 0 comments I used this same approach.

I remember I totally wasted an interview where I was asked for printing an array spirally. I struggled a lot there and here I had my successful submission. Feels good :)

alphaHaxor + 0 comments i did it similarly i think but timeout...

samar5yadav + 0 comments Good Logic bro!

RobertsN + 1 comment Did something similar but rather than flatten used deque's for each circle. However still failing #4,5 & 6 :( --> Not a question of int vs. long

Longest time 0.04 (C++ on test #9).

https://www.hackerrank.com/challenges/matrix-rotation-algo/submissions/code/25883205

Edit: was meant as a reply to ledmirage above but appeared down here instead.

RobertsN + 1 comment Actually found my problem. Algo works fine but I wasn't handling M>N properly.

victorgf + 1 comment Your problem was with a specific M or N? I am failing in the same cases and I cannot find the problem :(

RobertsN + 1 comment No, I was actually calculating when to stop flattening the matrix and had to use either N/2 or M/2 depending on which was bigger (+1 if odd).

victorgf + 1 comment Ok, thanks for your reply. Let's see how I solve this, with such big test cases seems impossible to see any pattern why they are failing.

pselamy + 0 comments I took a similar approach. Here is my Python 2 solution:

def build_grid(m, n, walls): grid = [[0 for j in xrange(n)] for i in xrange(m)] for w in xrange(len(walls)): wall = walls[w] wall_i = 0 for i in xrange(w, m - w): grid[i][w] = wall[wall_i] wall_i += 1 for j in xrange(1 + w, n - w): grid[-(1 + w)][j] = wall[wall_i] wall_i += 1 for i in xrange(-2 - w, -m - 1 + w, -1): grid[i][-(1 + w)] = wall[wall_i] wall_i += 1 for j in xrange(-2 - w, -n + w, -1): grid[w][j] = wall[wall_i] wall_i += 1 return '\n'.join(' '.join(map(str, row)) for row in grid) def get_rotated_grid(): m, n, r = map(int, raw_input().split()) grid = [map(int, raw_input().split()) for i in xrange(m)] walls = get_walls(m, n, grid) rotate_walls(r, walls) return build_grid(m, n, walls) def get_walls(m, n, grid): walls = [] while any(grid): wall = [] wall.extend(grid[i][0] for i in xrange(m)) wall.extend(grid[-1][j] for j in xrange(1, n)) wall.extend(grid[i][-1] for i in xrange(-2, -m - 1, -1)) wall.extend(grid[0][j] for j in xrange(-2, -n, -1)) walls.append(wall) grid = [grid[i][1:-1] for i in xrange(1, len(grid) - 1)] m -= 2 n -= 2 return walls def rotate_walls(r, walls): for i in xrange(len(walls)): wall = walls[i] wall_length = len(wall) rotations = r % wall_length walls[i] = wall[-rotations:] + wall[:-rotations]

The entrypoint is

`get_rotated_grid()`

quocbao100 + 0 comments Java recursion version

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static void matrixRotation(int[][] matrix, int si, int m, int n, int r) { if(m<1||n<1) return; int length = (m+n)*2; int[] flatMatrix= new int[length]; int index = 0; for(int i=0;i<=n;i++){ //top flatMatrix[index++] = matrix[si][si+i]; } for(int i=1;i<=m;i++){//right flatMatrix[index++] = matrix[si+i][si+n]; } for(int i=n-1;i>=0;i--){//bottom flatMatrix[index++] = matrix[si+m][si+i]; } for(int i=m-1;i>0;i--){//left flatMatrix[index++] = matrix[si+i][si]; } index = r % (length); for(int i=0;i<=n;i++){ //top matrix[si][si+i] = flatMatrix[(index++)%length]; } for(int i=1;i<=m;i++){//right matrix[si+i][si+n]= flatMatrix[(index++)%length]; } for(int i=n-1;i>=0;i--){//bottom matrix[si+m][si+i]= flatMatrix[(index++)%length]; } for(int i=m-1;i>0;i--){//left matrix[si+i][si]= flatMatrix[(index++)%length]; } matrixRotation(matrix, si+1,m-2,n-2,r); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); int r = in.nextInt(); int[][] matrix = new int[m][n]; for(int matrix_i = 0; matrix_i < m; matrix_i++){ for(int matrix_j = 0; matrix_j < n; matrix_j++){ matrix[matrix_i][matrix_j] = in.nextInt(); } } matrixRotation(matrix, 0 , m-1 , n-1,r); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ System.out.print(matrix[i][j]+" "); } System.out.println(); } in.close(); } }

ifazk + 1 comment There's actually no need to waste time physically rotating the matrix. Simply logicaly rotate it.

`for i = 0 to m - 1 do for j = 0 to n - 1 do let (x, y) = coordinates_before_rotation r (m, n) (i, j) in print_int mat.(x).(y); print_string " " done; print_string "\n"; done`

zakialam838 + 1 comment dude will you explain your concept ??

ifazk + 3 comments Suppose you are trying to rotate a 4x5 matrix by 9 places.

`1,1 1,2 1,3 1,4 1,5 2,1 2,2 2,3 2,4 2,5 3,1 3,2 3,3 3,4 3,5 4,1 4,2 4,3 4,4 4,5`

After rotation it will look like

`4,3 4,2 4,1 3,1 2,1 4,4 ........... 1,1 4,5 ........... 1,2 3,5 2,5 1,5 1,4 1,3`

So define a function that maps 1,1 to 4,3, 1,2 to 4,2, etc. There's no reason to actually rotate this in memory.

zakialam838 + 0 comments GEnius you are...:) you embraced my for loops by a mathematic logic

ppg_0007 + 1 comment how did u write the mapping function?

ifazk + 2 comments Firstly, a heads up, there's a fair amount of nasty case analysis involved. I don't want to give away the answer, but here's a hint: What is the most natural way to break down this problem into a group of smaller sub-problems?

lababa123 + 0 comments [deleted]gkatsanos + 2 comments Can you elaborate on the difference between physically and logically rotating the matrix?

I've only been on this for a little bit but to me it seems you need a bunch of checks (conditions) to see where your element is and then proceed to a necessary action (either increase/decrease i/j depending on where you are).

Am I too far off? Is there "another" more "generic" way to do this?

ifazk + 0 comments Physically rotating means you actually swap things around in memory, or create a new matrix with things in the right place. By logical rotation, I mean you never swap things around in memory. For each

`(i,j)`

pair, you logic out which value to print from the original matrix and then just print it.giaym + 0 comments instead of coord' = getNewCoordinates(coord), which will require you to write the results in memory before printing, you do coord = getPreviousCoordinates(coord') which allows you to print as soon as you get the result without using the memory anymore, as you stop writing you never "actually rotate" the matrix in-memory

Kevinagin + 0 comments I really like your way of thinking through the problem -- in terms of defining a function that maps indices. Thanks for posting this.

r3570r3 + 5 comments For those getting failures in testcase #7, #8, #9 and using Java, try thinking about the number of times you really need to rotate and limit your algorithm EVERYWHERE for it. There is enough hint in the other comments- mostly regarding modulo.

I figured I needed to limit when I got the timeouts and I tried with modulo. What I didn't realize was that inspite of using modulo deep within my code, I still had code that was executing unnecessarily from one of the parent loops.

If you have all the other cases passing, the only way to get through #7,#8,#9 is optimize optimize optimize.

the_shashwat + 0 comments thanks for this suggestion...it finally worked.

shahpujan1992 + 0 comments I also having same issue.. and didn't get exactly ur words but ur one word (OPTIMIZE) strike in my mind and changed the whole logic or loop logic of the probelm.. And its worked.. :) :)

gaurav4ever + 1 comment thanks man! I was stuck at the same point. I also optimised the number of time the matrix is rotating but still I was getting the same error. After reading your comment, the modulo concept strikes throught my mind. Finally got this! thanks again.

adityabyte1995 + 0 comments modulo logic is not working for me how to get it correct

StepanenkoVK + 0 comments I wasn't passing 8 and 9, found this embarassing snippet to be the problem:

while r >= circle: r-=circle

Thanks for reminding me that math exists :D

P.S.

r = r % circle

worked

IGomes + 1 comment I solve it creating arrays for each rotation. Like for example:

`6 4 7 1 2 3 4 16 17 18 5 15 24 19 6 14 23 20 7 13 22 21 8 12 11 10 9 [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], [17, 18, 19, 20, 21, 22, 23, 24, 0, 0, 0, 0, 0, 0, 0, 0]]`

0-Calculate n. of arrays and max for each one.

1-Read into arrays, in the write order.

2-Print arrays (i+rotation)%maxArr

Where in this example maxArr is 15 for 1st and 8 2nd.

(Read and Print is almost the same code to find the positions)

or this with 3 arrays

`6 7 1 1 2 3 4 5 6 7 22 23 24 25 26 27 8 21 36 37 38 39 28 9 20 35 42 41 40 29 10 19 34 33 32 31 30 11 18 17 16 15 14 13 12 [[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, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 0, 0, 0, 0, 0, 0, 0, 0], [37, 38, 39, 40, 41, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]`

and so forth.

https://www.hackerrank.com/challenges/matrix-rotation-algo/submissions/code/57157720

phoemur + 0 comments I solved it the same way. But i definetily underestimated this one, took me a lot of time to get all tests passing...

kmjayadeep + 0 comments finally cracked it! thanks for all the suggestions Here is my java code

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { int r,c,n; Scanner s= new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); n = s.nextInt(); int[][] mat = new int[r][c]; int[][] res = new int[r][c]; for(int i=0;i<r;i++) for(int j=0;j<c;j++) mat[i][j] = s.nextInt(); for(int i=0;i<r;i++) for(int j=0;j<c;j++){ int row = i,col = j; int layer = Math.min(Math.min(i,j),Math.min(r-i-1,c-j-1)); int param = (r+c-2)*2-8*layer; //no of elements in array if(param==0){ res[i][j] = mat[i][j]; return; } int rot = n%param; while(rot-->0){ if(row==layer&&col==layer) row++; else if(row==layer&&col==c-layer-1) col--; else if(row==r-layer-1&&col==layer) col++; else if(row==r-layer-1&&col==c-layer-1) row--; else if(row==layer) col--; else if(col==layer) row++; else if(row==r-layer-1) col++; else if(col==c-layer-1) row--; } // System.out.println(row+" "+col+" by "+i+" "+j); res[row][col] = mat[i][j]; } for(int i=0;i<r;i++){ for(int j=0;j<c;j++) System.out.print(res[i][j]+" "); System.out.println(); } } }

saltaverde + 1 comment My output is identical to the expected output, but all test cases are marked as 'wrong answer'. Any ideas???

smartsammy787 + 1 comment remove any extra empty output lines from code.In my case I removed system.out... line while taking input. Read this. http://support.hackerrank.com/customer/portal/articles/1943759-faq-on-test-environment

saltaverde + 0 comments Thanks, that did the trick!

gerome_pistre + 2 comments Relatively simple (and fast) solution in python 2:

`m, n, r = [int(i) for i in raw_input().strip().split(' ')] mat = [[int(i) for i in raw_input().strip().split(' ')] for _ in xrange(m)] def printMat(mat): for row in mat: for elem in row: print elem, print def rotateMatrix(matr, r): offset = 0 while n - offset > n / 2 and m - offset > m / 2: top = [(offset, i) for i in range(offset, n - offset, 1)] right = [(i, n - 1 - offset) for i in range(offset + 1, m - 1 - offset, 1)] bot = [(m - 1 - offset, i) for i in range(n - 1 - offset, offset - 1, -1)] left = [(i, offset) for i in range(m - offset - 2, offset, -1)] idx = top + right + bot + left circle = [matr[p[0]][p[1]] for p in idx] rMod = r % len(circle) circle = circle[rMod:] + circle[0:rMod] for q in range(len(idx)): index = idx[q] matr[index[0]][index[1]] = circle[q] offset += 1 return matr printMat(rotateMatrix(mat, r))`

rahulranjan93 + 0 comments ingenious :)

cgrs27 + 0 comments i was thinking in trying with circles rotation but i find more easy wit displacements.

Dante_vergil + 1 comment getting timeout for 7,8,9.please suggest me how to optimize

ajk100Asked to answer + 2 comments Don't iterate all blocks r times... Just calculate number of times each block needs to be rotated:)

qiji1hit + 1 comment perfect answer

pkoeck + 3 comments Hint: The mod operator is your friend.

vipul_sharma + 0 comments Nice Question

SVMarshall + 0 comments [deleted]ryanpacesloan + 0 comments Yes it is thanks!

hardikaghara1012 + 1 comment i am face same problem. can you explain me in detail?

amazingheo + 0 comments Each layer is same as a circle. So, after rotate the layer by n times, its state will return to origin. Therefore, we can reduce the total number of rotate using the modulo operation.

Sort 421 Discussions, By:

Please Login in order to post a comment