Matrix Layer Rotation

Sort 365 Discussions, By:

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

lol

• foxcrocode + 1 comment

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

LMAO _

[deleted]

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

• VB

Finally Done !!

Almost sucked all my blood out over it

Nice question :)

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

• MB

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

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

• JG

:D Burn!!

• SV

Nailed it bro!!:p

• RC
[deleted]
• X

hi, Im having hard time breaking through developing my logic skills, is there any book or documentation you recommend to read about?

• P

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

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.

• M
Mudit_gupta_13 + 1 comment

http://www.geeksforgeeks.org/rotate-matrix-elements/

• SN

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

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.

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.

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

[deleted]

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;
}


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) ".

r < rows - r ? r : rows - r is simply min(r, rows - r).

• HT

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

• DG

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

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

pretty amazing. thx

• AS

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.

brother pls explain me logic

• GK

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

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.

• AB

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++){
}
for(int i = 0+layer; i < h-1-layer; i++){
}
for(int i = w-1-layer; i > 0+layer; i--){
}
for(int i = h-1-layer; i > 0+layer; i--){
}
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();
}

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


You're brilliant.

[deleted]

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?

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.

• M

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.

• pulikutti + 1 comment

thanks, but it is mentioned in the specification that it has to be rotated by one position in one rotation?

then why do they give you R

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


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.

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.

• SS
sharmasim319 + 1 comment

can you please explain the use of bottom for loop

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.

• MW

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;


}

• RB

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;

• SK

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 ?

• HG

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

or you can also using (m*n-(m-2)*(n-2))

This approach didn't work for me. :(

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

• P

This is great solution. Bravo !!!

• JP

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.

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


}

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

i did it similarly i think but timeout...

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

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.

• VG
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).

• VG
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.

• VG
victorgf + 1 comment

Finally, I could solve the challenge and your comment (RobertsN) helped me a lot. Thank you very much!

• PS

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

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

• IK
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

• ZA
zakialam838 + 1 comment

dude will you explain your concept ??

• IK

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.

• ZA

GEnius you are...:) you embraced my for loops by a mathematic logic

• ppg_0007 + 1 comment

how did u write the mapping function?

• IK

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?

[deleted]

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?

• IK

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.

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

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

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.

• axbui + 1 comment

can you elaborate, please? I'm having issues and I'm not sure how to optimize. I'm currently doing modulo on the outtermost layer, should i perform a mod on every layer?

Yes. Use modulo throughout.

thanks for this suggestion...it finally worked.

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.

modulo logic is not working for me how to get it correct

• saltaverde + 1 comment

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

• SH
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

Thanks, that did the trick!

• J

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 + 1 comment

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

• RR

ingenious :)

• Dante_vergil + 1 comment

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

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

• JQ
qiji1hit + 1 comment

• PK

Hint: The mod operator is your friend.

• V

Nice Question

[deleted]
• RP

Yes it is thanks!

• 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