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