Rotating a two dimensional array by 90 degrees

Question

I am studying this piece of code on rotating an NxN matrix; I have traced the program countless times, and I sort of understand how the actual rotation happens. It basically rotates the corners first and the elements after the corners in a clockwise direction. I just do not understand a couple of lines, and the code is still not "driven home" in my brain, so to speak. Please help. I am rotating it 90 degrees, given a 4x4 matrix as my tracing example.

[1][2][3][4] 
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

becomes

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]

---

public static void rotate(int[][] matrix, int n){
  for(int layer=0; layer < n/2; ++layer) {
     int first=layer; //It moves from the outside in. 
     int last=n-1-layer; //<--This I do not understand  
     for(int i=first; i<last;++i){
       int offset=i-first; //<--A bit confusing for me

       //save the top left of the matrix 
       int top = matrix[first][i];

       //shift left to top; 
       matrix[first][i]=matrix[last-offset][first]; 
       /*I understand that it needs
        last-offset so that it will go up the column in the matrix,
       and first signifies it's in the first column*/

       //shift bottom to left 
       matrix[last-offset][first]=matrix[last][last-offset];
        /*I understand that it needs
        last-offset so that the number decreases and it may go up the column (first 
        last-offset) and left (latter). */

       //shift right to bottom
       matrix[last][last-offset]=matrix[i][last];
        /*I understand that it i so that in the next iteration, it moves down 
        the column*/        



       //rightmost top corner
        matrix[i][last]=top;
       }
   }

}

Answer 1

It's easier to understand an algorithm like this if you draw a diagram, so I made a quick pic in Paint to demonstrate for a 5x5 matrix :D

The outer for(int layer=0; layer < n/2; ++layer) loop iterates over the layers from outside to inside. The outer layer (layer 0) is depicted by coloured elements. Each layer is effectively a square of elements requiring rotation. For n = 5, layer will take on values from 0 to 1 as there are 2 layers since we can ignore the centre element/layer which is unaffected by rotation. first and last refer to the first and last rows/columns of elements for a layer; e.g. layer 0 has elements from Row/Column first = 0 to last = 4 and layer 1 from Row/Column 1 to 3.

Then for each layer/square, the inner for(int i=first; i<last;++i) loop rotates it by rotating 4 elements in each iteration. Offset represents how far along the sides of the square we are. For our 5x5 below, we first rotate the red elements (offset = 0), then yellow (offset = 1), then green and blue. Arrows 1-5 demonstrate the 4-element rotation for the red elements, and 6+ for the rest which are performed in the same fashion. Note how the 4-element rotation is essentially a 5-assignment circular swap with the first assignment temporarily putting aside an element. The //save the top left of the matrix comment for this assignment is misleading since matrix[first][i] isn't necessarily the top left of the matrix or even the layer for that matter. Also, note that the row/column indexes of elements being rotated are sometimes proportional to offset and sometimes proportional to its inverse, last - offset.

We move along the sides of the outer layer (delineated by first=0 and last=4) in this manner, then move onto the inner layer (first = 1 and last = 3) and do the same thing there. Eventually, we hit the centre and we're done.