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