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 } } }
The rotation of a matrix involves two steps: First, find the transpose of the given matrix. Swap the elements of the first column with the last column (if the matrix is of 3*3). The second column remains the same.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With