google-code-prettify

Thursday 3 January 2013

Rotate Matrix

Here is another Google interview question (http://www.careercup.com/question?id=14891673):
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.
Rotate Matrix

5 comments:

  1. /* 3 x 3 Matrix rotation code, could work for any size */

    int c = 0;
    while (c < 3) {
    r = 2;
    while(r >= 0) {
    System.out.print(mtx[r][c] + ".");
    r--;
    }
    System.out.println();
    c++;
    }

    ReplyDelete
  2. This is a very elegant solution. Thanks!
    The 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++;
    }
    }

    ReplyDelete
  3. Can you please explain how you get those for loop constraints ? And why there are sufficient ?

    ReplyDelete
    Replies
    1. The 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).
      The 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).

      Delete