Given a matrix represented as int[n][n], rotate it 90 degrees clockwise in-place. (In-place means minimal extra memory to be used, i.e. don't make a new array to copy into). Rotate clockwise means top-row becomes right-column, right column becomes bottom-row etc.
In the solution uses one extra integer variable to rotate elements in each iteration. There are two for loops - the outer one deals with one layer of the matrix per iteration, while the inner one deals with rotation of the elements of the layers.
void rotateMatrix(int a[][]) {
int n = a.length;
if (n <= 1) {
return; // nothing to do
}
/* layers */
for (int i = 0; i < n / 2; i++) {
/* elements */
for (int j = i; j < n - i - 1; j++) {
int saved = a[i][j];
a[i][j] = a[n - j - 1][i];
a[n - j - 1][i] = a[n - 1 - i][n - 1 - j];
a[n - 1 - i][n - 1 - j] = a[j][n - 1 - i];
a[j][n - 1 - i] = saved;
}
}
}
In the picture below you can see the different layers in different colours. It shows what happens after each iteration of the outer for loop.
/* 3 x 3 Matrix rotation code, could work for any size */
ReplyDeleteint c = 0;
while (c < 3) {
r = 2;
while(r >= 0) {
System.out.print(mtx[r][c] + ".");
r--;
}
System.out.println();
c++;
}
This is a very elegant solution. Thanks!
ReplyDeleteThe function would be:
void rotateMatrix2(int mtx[][]) {
int c = 0;
int r = 0;
int length = mtx.length;
while (c < length) {
r = length - 1;
while (r >= 0) {
System.out.print(mtx[r][c] + ".");
r--;
}
System.out.println();
c++;
}
}
Can you please explain how you get those for loop constraints ? And why there are sufficient ?
ReplyDeleteThe outer loop's constraints are easily seen on the picture, i.e. the number of layers is n/2 (for odd n - there is an element in the middle which stays there after the matrix rotation).
DeleteThe inner loop's constraints again can be seen on the picture - every layer that gets closer to the middle of the matrix contains 2 elements less (in a row/column) than the previous layer. The inner loop's constraints depend on the number of layer (j = i & j < n - i - 1) and i is increased by one in each outer loop iteration and that is how we fulfill the previews requirement (for 2 elements less in the next inner loop iteration).
Hi mine is a similar solution with O(n^2) time and O(1) space - http://k2code.blogspot.in/2014/03/rotate-n-n-matrix-by-90-degrees.html
ReplyDelete