Rotating a NxN matrix in Java

Question

This is a question from Cracking the Coding Interview. The solution says that the program rotates the exterior edges, then the interior edges. However, I'm having trouble following the logic of both the for loops.

Could somebody explain the logic of the code (e.g. why they do "layer < n/2" and the four steps of "left -> top" and "bottom -> left" etc)? On a side note, how would one's thought process be when coming up with this during a coding interview?

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

public static void rotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; ++layer) {
        int first = layer;
        int last = n - 1 - layer;
        for(int i = first; i < last; ++i) {
            int offset = i - first;
            int top = matrix[first][i]; // save top

            // left -> top
            matrix[first][i] = matrix[last-offset][first];          

            // bottom -> left
            matrix[last-offset][first] = matrix[last][last - offset]; 

            // right -> bottom
            matrix[last][last - offset] = matrix[i][last]; 

            // top -> right
            matrix[i][last] = top; // right <- saved top
        }
    }
}

Answer 1

Overview

Consider a sample matrix could look like this:

ABCD
EFGH
IJKL
MNOP

For the purposes of my explanation, ABCD is considered as row 0, EFGH is row 1, and so on. The first pixel of row 0 is A.

Also, when I talk about the outer shell, I am referring to:

ABCD
E  H
I  L
MNOP

First let's look at the code that moves the values.

    int top = matrix[first][i]; // save top

The first line caches the value in the top position. This refers to the position on the top row of the matrix identified by [first][i]. Eg: saving the A.

    // left -> top
    matrix[first][i] = matrix[last-offset][first];          

The next part moves the value from the left position into the top position. Eg: taking the M and putting it where the A is.

    // bottom -> left
    matrix[last-offset][first] = matrix[last][last - offset]; 

The next part moves the value from the bottom position into the left position. Eg: taking the P and putting it where the M is.

    // right -> bottom
    matrix[last][last - offset] = matrix[i][last]; 

The next part moves the value from the right position into the bottom position. Eg: taking the D and putting it where the P is.

    // top -> right
    matrix[i][last] = top; // right <- saved top

The last part moves the value from the cache (what was the top position) into the right position. Eg: putting the A from the first step where the D is.

Next the loops.

The outer loop runs from row 0 to half the total number of rows. This is because when you rotate row 0, it also rotates the last row and when you rotate row 1, it also rotates the second-to-last row, and so on.

The inner loop runs from the first pixel position (or column) in the row to the last. Keep in mind that for row 0, this is from pixel 0 to the last pixel, but for row 1, this is from pixel 1 to the second-to-last pixel, since the first and last pixels are rotated as part of row 0.

So the first iteration of the outer loop makes the outer shell rotate. In other words:

ABCD
EFGH
IJKL
MNOP

becomes:

MIEA
NFGB
OJKC
PLHD

See how the outer shell has rotated clockwise, but the inner core has not moved.

Then the second iteration of the outer loop causes the second row to rotate (excluding the first and last pixels) and we end up with:

MIEA
NJFB
OKGC
PLHD