Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOTallocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Algorithm:

It's simply moving numbers around, and you only need to find the rules.

for N = 3, you only need to move the outside edge twice :

1 2 3    a   7 2 1     b     7 4 1

4 5 6  ==> 4 5 6  ==>   8 5 2

7 8 9         9 8 3           9 6 3  

To achieve step a :                                                Note that if we want to rotate left:

tmp = (0, 0)          // Throw 1 in tmp                       tmp = (0, 0)

(0, 0) = (2, 0)       // Replace 1 with 7                     (0, 0) = (0, 2)

(2, 0) = (2, 2)       // Replace 7 with 9                     (0, 2) = (2, 2)

(2, 2) = (0, 2)       // Replace 9 with 3                     (2, 2) = (2, 0)

(0, 2) = tmp         // Replace 3 with 1                     (2, 0) = tmp

Same idea you can get step b :

With these coordinates mapping from step a & b, you can get something like this:

1 2 3 4 5 6 7

for(int i=0; i < nn-1; i++) { int tmp = matrix[0][i]; matrix[0][i] = matrix[nn-1-i][0]; matrix[nn-1-i][0] = matrix[nn-1][nn-1-i]; matrix[nn-1][nn-1-i] = matrix[i][nn-1]; matrix[i][nn-1] = tmp; }

But then you realize that this only rotate the outside rim.

For N=4 :

1    2    3   4                 13   9   5    1           c          13   9  5  1
5    6    7   8       =>     14   6   7    2         ===>     14  10  6  2
9   10  11 12                15  10  11  3                       15  11  7  3
13 14  15 16                16  12  8    4                       16  12  8  4

We need extra loop to move the highlighted area (Step c) :

tmp   =  (1, 1)
(1, 1) =  (2, 1)
(2, 1) =  (2, 2)
(2, 2) =  (1, 2)
(1, 2) =  tmp

It's not hard to figure out the final from here.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[][] matrix) { int nn = matrix[0].length; for(int j=0; j < nn/2; j++ ) { for(int i=j; i < nn-1-j; i++) { int tmp = matrix[j][i]; matrix[j][i] = matrix[nn-1-i][j]; matrix[nn-1-i][j] = matrix[nn-1-j][nn-1-i]; matrix[nn-1-j][nn-1-i] = matrix[i][nn-1-j]; matrix[i][nn-1-j] = tmp; } } } }

For comparison, this is the solution for rotate left by 90 degree:

  static void rotateLeft2D(int[][] matrix)
  {
    int nn = matrix[0].length;
    for(int j=0; j < nn/2; j++ ) {
      for(int i=j; i < nn-1-j; i++) {
        int tmp = matrix[j][i];
        matrix[j][i] = matrix[i][nn-1-j];
        matrix[i][nn-1-j] = matrix[nn-1-j][nn-1-i];
        matrix[nn-1-j][nn-1-i] = matrix[nn-1-i][j];
        matrix[nn-1-i][j] = tmp;
      }
    }
  }

Performance: