Loading...

Sort 365 Discussions, By:

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

    • nikhilksingh + 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 :)

  • VB
    Visharad_05 + 4 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.

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

        • JG
          gangaj + 0 comments

          :D Burn!!

        • SV
          surajvermav38 + 0 comments

          Nailed it bro!!:p

      • RC
        rchavez + 0 comments
        [deleted]
      • X
        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 !

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

        • M
          Mudit_gupta_13 + 1 comment

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

          • SN
            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?

      • 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 + 6 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).

        • HT
          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
          
        • DG
          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

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

      • GK
        gnakum7845 + 0 comments

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

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

      • AB
        _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.

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

        • pulikutti + 1 comment

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

          • giaym + 0 comments

            then why do they give you R

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

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

          • MW
            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;
            

            }

          • RB
            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;
            
    • SK
      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 ?

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

    • P
      persoy + 0 comments

      This is great solution. Bravo !!!

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

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

                • RobertsN + 0 comments

                  Glad I could help :)

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

        • ZA
          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?

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

              • IK
                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 + 4 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.

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

      • r3570r3 + 0 comments

        Yes. Use modulo throughout.

    • 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

  • 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

      • saltaverde + 0 comments

        Thanks, that did the trick!

  • J
    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();
            }
            
        }
    }
    
  • 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
      rahulranjan93 + 0 comments

      ingenious :)

  • Dante_vergil + 1 comment

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

    • ajk100Asked to answer + 1 comment

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

      • JQ
        qiji1hit + 1 comment

        perfect answer

        • PK
          pkoeck + 3 comments

          Hint: The mod operator is your friend.

          • V
            vipul_sharma + 0 comments

            Nice Question

          • SVMarshall + 0 comments
            [deleted]
          • RP
            ryanpacesloan + 0 comments

            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

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