## Matrix Layer Rotation

Morihei 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 ))

nikhilksingh lol

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

shubhamitankr LMAO

*_*

tolgahanalbayrak [deleted]NAklecha # 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 Finally Done !!

Almost sucked all my blood out over it

Nice question :)

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

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

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

gangaj :D Burn!!

surajvermav38 Nailed it bro!!:p

rchavez [deleted]xayuzaii 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 Work through easier problems first and then come back for the difficult ones like this one is

kaosreigns 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 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 The solution presented is the brute force algorithm that will time out for large matrices. Maybe I'm reading it wrong?

yerzhik 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 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 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 True. It is not a hard problem. I am an average guy. I found many easy/medium questions much harder than this one.

tolgahanalbayrak [deleted]

etayluz 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 What's the logic behind:

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

?

kaosreigns 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 `r < rows - r ? r : rows - r`

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

.

hackest 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 variable min is the layer number of the matrix.. to find that we have to do the above calculation.

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

maximshen pretty amazing. thx

asapper1 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 brother pls explain me logic

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

alphaHaxor 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 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 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 You're brilliant.

alphaHaxor [deleted]

shamim_hafiz 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 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 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 test case 7, 8 and 9 are failing due to timeout error.. can you pls help

giaym 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.

ledmirage 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 holy moly, never thought about the problem like this :/

avinashshenoy97 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 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 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 can you please explain the use of bottom for loop

avinashshenoy97 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 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 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 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 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 or you can also using (m*n-(m-2)*(n-2))

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

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

persoy This is great solution. Bravo !!!

madbrain 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 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 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 i did it similarly i think but timeout...

samar5yadav Good Logic bro!

RobertsN 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 Actually found my problem. Algo works fine but I wasn't handling M>N properly.

pselamy 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 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 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 dude will you explain your concept ??

ifazk 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 GEnius you are...:) you embraced my for loops by a mathematic logic

ppg_0007 how did u write the mapping function?

ifazk 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 [deleted]gkatsanos 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 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 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 I really like your way of thinking through the problem -- in terms of defining a function that maps indices. Thanks for posting this.

r3570r3 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 thanks for this suggestion...it finally worked.

shahpujan1992 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 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 modulo logic is not working for me how to get it correct

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

smartsammy787 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 Thanks, that did the trick!

kmjayadeep 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(); } } }

gerome_pistre 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 ingenious :)

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

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

qiji1hit perfect answer

pkoeck Hint: The mod operator is your friend.

vipul_sharma Nice Question

SVMarshall [deleted]ryanpacesloan Yes it is thanks!

IGomes 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 I solved it the same way. But i definetily underestimated this one, took me a lot of time to get all tests passing...

Sort 365 Discussions, By:

Please Login in order to post a comment