How to rotate a N x N matrix by 90 degrees?

Question

How to rotate a N x N matrix by 90 degrees. I want it to be inplace?

Duplicate of [How do you rotate a two dimensional array?](http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array) (the code in those solutions is mostly not C++, but the algorithms are straightforward enough that converting to C++ should be trivial in most cases) — James McNellis, May 23 '10 at 19:29
That depends on how the matrix is stored in your data structure. What have you tried so far? — Greg Hewgill, May 23 '10 at 19:29
Clockwise, please make sure that you don't create a extra matrix. — Passionate programmer, May 23 '10 at 19:33
@James, the question you linked to doesn't require rotation to be in-place, and none of the answers suggests such a solution. — P Shved, May 23 '10 at 19:34
@Pavel: Well, there was no in-place requirement in the question when I posted that. It appears the OP has modified the requirements. — James McNellis, May 23 '10 at 19:37
I've been seeing so many of these rotation questions lately but what exactly matrix rotation means is the harder question I guess. — nikhil, Mar 10 '13 at 16:03

score 57 · Accepted Answer · edited Dec 27 '10 at 22:12

57

for(int i=0; i<n/2; i++)
   for(int j=0; j<(n+1)/2; j++)
       cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]);


void cyclic_roll(int &a, int &b, int &c, int &d)
{
   int temp = a;
   a = b;
   b = c;
   c = d;
   d = temp;
}

Note I haven't tested this, just compoosed now on the spot. Please test before doing anything with it.

edited Dec 27 '10 at 22:12

Kiril

39,672
31
167
226

answered May 23 '10 at 19:32

Pavel Radzivilovsky

18,794
5
57
67

could you explain on how did you come up with the indexes ? – Passionate programmer May 23 '10 at 19:38
4

Explaining the indexes.. well, think where the location at (i,j) goes when rotating 90 degrees. Just imagine the picutre. (i,j)->(end-j, i). As high as the original was far from the left, and as far from the left as it was from the bottom of the matrix. – Pavel Radzivilovsky May 23 '10 at 19:42
2

If one rotates counter-clockwise, the mapping is a[p][k] --> a[N-1-k][p] --> a[N-1-p][N-1-k] --> a[k][N-1-p]. I think there is also an error in the constrain for i. It should be i < n/2 in the for loop (for j it's ok). Look at the 3x3 example below. Number 4 gets taken care of, when rotating 2. You don't want to rotate for i = 1 and j = 0 again. – Maciej Hehl May 23 '10 at 19:50
4

I can't edit. The code should be for(int i=0; i < N/2; i++) for(int j=0; j < (N+1)/2; j++) cyclic_roll(a[i][j], a[N-1-j][i], a[N-1-i][N-1-j], a[j][N-1-i]); – Maciej Hehl May 23 '10 at 20:45
2

The third parameter to the cyclic_roll function still needs a correction. It Should be a[n-1-i][n-1-j] :) – Maciej Hehl May 23 '10 at 21:38
1

OK, Pavel... you rotation counter-clockwise, right? I think the OP asked for a clockwise rotation, so I just want to point out that whoever is looking at this answer should keep that in mind and not just blindly copy and paste :). – Kiril Dec 27 '10 at 22:17

score 11 · Answer 2 · edited Jan 30 '16 at 12:29

11

here is my solution: (rotate pi/2 clockwise)

do the transpose of the array, (like matrix transpose)

reverse the elements for each row

cons int row = 10;
cons int col = 10;
//transpose
for(int r = 0; r < row; r++) {
  for(int c = r; c < col; c++) {  
    swap(Array[r][c], Array[c][r]);
  }
}
//reverse elements on row order
for(int r = 0; r < row; r++) {
    for(int c =0; c < col/2; c++) {
      swap(Array[r][c], Array[r][col-c-1])
    }
}

if rotate pi/2 in counter-clockwise

transpose the array
reverse the elements on column order

never test the code! any suggestion would be appreciated!

edited Jan 30 '16 at 12:29

rrk

15,677
4
29
45

answered Aug 03 '11 at 04:43

elliptic00

427
4
13

1

Each element will be moved twice (compared to 1.25 times in @Pavel Radzivilovsky's answer), so this is less efficient. The "upside" is that since there is no need for an `int temp`, the memory requirement is reduced by all of four bytes... – Jean-François Corbett Aug 03 '11 at 06:18
2

agreed with @Jean-FrançoisCorbett not as efficient as the other ans. But, this one is simpler for sure. Actually, i also implemented same algo!! – MalTec Jul 28 '12 at 19:55
1

thanks this greatly simplifies the solution – Validus Oculus Mar 15 '15 at 13:13

Chetan Narsude · Answer 3 · 2012-06-07T04:45:43.310

A complete C program which illustrates my approach. Essentially it's recursive algo. At each recursion you rotate the outer layer. Stop when your matrix is 1x1 or 0x0.

#include <stdio.h>

int matrix[4][4] = {
     {11, 12, 13, 14},
     {21, 22, 23, 24},
     {31, 32, 33, 34},
     {41, 42, 43, 44} 
};

void print_matrix(int n)
{
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         printf(" %d ", matrix[i][j]);
      }
      printf("\n");
   }
}

int *get(int offset, int x, int y)
{
   return &matrix[offset + x][offset + y];
}

void transpose(int offset, int n)
{
   if (n > 1) {
      for (int i = 0; i < n - 1; i++) {
         int *val1 = get(offset, 0, i);
         int *val2 = get(offset, i, n - 1);
         int *val3 = get(offset, n - 1, n - 1 - i);
         int *val4 = get(offset, n - 1 - i, 0);

         int temp = *val1;
         *val1 = *val4;
         *val4 = *val3;
         *val3 = *val2;
         *val2 = temp;
      }

      transpose(offset + 1, n - 2);
   }
}

main(int argc, char *argv[])
{
   print_matrix(4);
   transpose(0, 4);
   print_matrix(4);
   return 0;
}

score 0 · Answer 4 · edited Aug 20 '14 at 08:29

//Java version, fully tested

public class Rotate90degree {


        public static void reverseElementsRowWise(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n / 2; ++j) {
                    int temp = matrix[i][n - j - 1];
                    matrix[i][n - j - 1] = matrix[i][j];
                    matrix[i][j] = temp;
                }
            }
        }

        public static void transpose(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = i + 1; j < n; ++j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }

        public static void rotate90(int[][] matrix) {
            transpose(matrix);
            reverseElementsRowWise(matrix);
        }

        public static void print(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    System.out.print(matrix[i][j]);
                    System.out.print(' ');
                }
                System.out.println();
            }
        }

        public static void main(String[] args) {
            int[][] matrix = {
                    {1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}};
            System.out.println("before");
            print(matrix);
            rotate90(matrix);
            System.out.println("after");
            print(matrix);
        }
}

score -5 · Answer 5 · answered May 23 '10 at 19:31

You could create a second array and then copy the first one into the second one by reading row-major in the first one and writing column-major to the second one.

So you would copy:

1  2  3
4  5  6
7  8  9

and you would read the first row then write it back up starting like:

3
2
1

How to rotate a N x N matrix by 90 degrees?

5 Answers5

Linked

Related