Following is a java solution of the classic question of rotating a nxn matrix in place clockwise by 90 degrees.
public 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;
// save top
int top = matrix[first][i];
// 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;
}
}
}
Below is the approach I am try to use: 1. Understand the problem statement, assumptions. 2. Break problem in smallest sub-tasks and try to write/explain the solution as plain english. 3. Write pseudo code 4. Write actual code.
I am getting stuck between #3 and #4. I have the approach and know the logic, but am having a hard time in writing a part of the solution. Let me show what:
Approach: Given this nxn matrix:
[00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33]
This matrix can be rotated by rotating the the highlighted inner and outer rings (not actually circular). The outer ring has *.
[00* 01* 02* 03*
10* 11 12 13*
20* 21 22 23*
30* 31* 32* 33*]
Now, to rotate the rows and columns, each element of the rows and corresponding column can be moved. For example, first take 00 in a temporary variable. Move 30 in place of 00. Move 33 in place of 30. Move 03 in place of 33 and finally assign temp to 03. Similarly, move the others.
Now, the above approach can be implemented by taking an outer counter between 0 and less than len/2. This is called as layer in the solution. Inner counter will be between layer and last. Simple!
But, I am having a hard time in coding the part in bold. i.e. writing below to work for all indexes.
// save top
// left -> top
// bottom -> left
// right -> bottom
// top -> right
i.e the things between []: Gave the question a break, but kept making mistakes in any one of these dynamic indexes. I am usually comfortable in nested/normal loops.
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last - offset];
matrix[last][last - offset] = matrix[i][last];
matrix[i][last] = top;
I know what needs to be done but cannot write the logic of dynamic indexes. Any help on this will be appreciated. The solution is there, but this question is more of a helpful advice. What do/did you do when stuck like this?
The above answer has been explained by the author, but she also skipped to the already written program after explaining the approach.
