90-degree rotation of a two-dimensional array

Question

I study this piece of code while rotating the NxN matrix; I have tracked the program countless times and I understand how the actual rotation happens. It basically rotates corners first and elements after corners clockwise. I just don’t understand a couple of lines, and the code, in my opinion, is still not “catching up” in my brain. Please help. I rotate it 90 degrees, given a 4x4 matrix as an example of tracing.

[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 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 such an algorithm if you are drawing a chart, so I did a quick review in Paint to demonstrate the 5x5: D matrix

The outer for(int layer=0; layer < n/2; ++layer) loop for(int layer=0; layer < n/2; ++layer) iterates through the layers outside and inside. The outer layer (layer 0) is represented by colored elements. Each layer is actually a square of elements requiring rotation. For n = 5, the layer will take values ​​from 0 to 1, since there are 2 layers, since we can ignore the central element / layer, which is not subject to the influence of rotation. the first and last refer to the first and last rows / columns of elements for the layer; for example, layer 0 has elements from the row / column first = 0 for last = 4 and layer 1 from the row / column 1 to 3.

Then for each layer / square, the inner for(int i=first; i<last;++i) loop for(int i=first; i<last;++i) rotates it by rotating 4 elements in each iteration. The 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 show 4-element rotation for red elements, and for the rest - 6+, which are performed equally. Notice how 4-element rotation is essentially a circular change with 5 assignments, with the first assignment temporarily deferring the element. Comment //save the top left of the matrix for this purpose is misleading, because the matrix [first] [i] is not necessarily in the upper left corner of the matrix or even the layer in this regard. Also note that the row / column indices of rotating elements are sometimes proportional to the offset and sometimes proportional to its inverse, the latter to the offset.

Thus, we move along the sides of the outer layer (marked first = 0 and last = 4), then go to the inner layer (first = 1 and last = 3) and do the same. In the end, we got to the center, and everything is ready.

Answer 2

This causes WTF. The easiest way to rotate the matrix into place is to

• first transfer the matrix (swap M [i, j] with M [j, i])
• then replacing M [i, j] with M [i, nColumns - j]

When matrices have a column size, the second operation is the exchange of columns and, therefore, has good data locality properties. If the matrix is ​​a row, first rearrange the rows, and then transpose.

Answer 3

Here is a recursive way to resolve this issue:

// rotation of the array 2 D (mXn) 90 degrees

 public void rotateArray(int[][] inputArray) { System.out.println("Input Array: "); print2D(inputArray); rotateArray(inputArray, 0, 0, inputArray.length - 1, inputArray[0].length - 1); System.out.println("\n\nOutput Array: "); print2D(inputArray); } public void rotateArray(int[][] inputArray, int currentRow, int currentColumn, int lastRow, int lastColumn) { // condition to come out of recursion. // if all rows are covered or all columns are covered (all layers // covered) if (currentRow >= lastRow || currentColumn >= lastColumn) return; // rotating the corner elements first int top = inputArray[currentRow][currentColumn]; inputArray[currentRow][currentColumn] = inputArray[lastRow][currentColumn]; inputArray[lastRow][currentColumn] = inputArray[lastRow][lastColumn]; inputArray[lastRow][lastColumn] = inputArray[currentRow][lastColumn]; inputArray[currentRow][lastColumn] = top; // clockwise rotation of remaining elements in the current layer for (int i = currentColumn + 1; i < lastColumn; i++) { int temp = inputArray[currentRow][i]; inputArray[currentRow][i] = inputArray[lastRow - i][currentColumn]; inputArray[lastRow - i][currentColumn] = inputArray[lastRow][lastColumn - i]; inputArray[lastRow][lastColumn - i] = inputArray[currentRow + i][lastColumn]; inputArray[currentRow + i][lastColumn] = temp; } // call recursion on remaining layers rotateArray(inputArray, ++currentRow, ++currentColumn, --lastRow, --lastColumn); }