Matrix Rotation

Given a square matrix of dimension N, Rotate the matrix clockwise/anti-clockwise. Example:

1   2   3   4                                      13  9   5   1
5   6   7   8           Rotating clockwise         14  10  6   2    
9   10  11  12          ------------------->       15  11  7   3
13  14  15  16                                     16  12  8   4
Approach 1:

Take another array or same size NxN. Replace each element of original matrix into new matrix correctly.

  • Complexity: O(N^2)
  • Space: O(N^2)

Cons: In case grid is too large, space complexity O(N^2) too bad.

Approach 2:

In this approach we don't need any additional memory. Swapping elements layer by layer will give a rotated matrix. Consider a matrix of size 5x5. Notice the layers in following matrix. Red color indicates layer 1, Green color indicates layer 2, Black color indicates layer 3.

In layer 1,
1 goes to position of  5,  5 -> 25, 25 -> 21, 21 -> 1
2 goes to position of 10, 10 -> 24, 24 -> 16, 16 -> 2
...

In layer 1, following elements should be swapped:
(0, 0) -> (0, N-1) -> (N-1, N-1) -> (N-1, 0)
(0, 1) -> (1, N-1) -> (N-1, 3)   -> (3,   0)
(0, 2) -> (2, N-1) -> (N-1, 2)   -> (2,   0)
(0, 3) -> (3, N-1) -> (N-1, 1)   -> (1,   0)

In layer 2, following elements should be swapped:
(1, 1) -> (1, N-1-1) -> (N-1-1, N-1-1) -> (N-1-1, 1)
(1, 2) -> (2, N-1-1) -> (N-1-1, N-1-2) -> (N-1-2, 2)

In general: For each layer "layer" and each "i" where i = layer to N-1-layer
(layer, i) -> (i, N-1-layer) -> (N-1-layer, N-1-i) -> (N-1-i, layer)
  • Complexity: O(N^2)
  • Space: O(1)

One disadvantage of this approach is finding the general index formula is hard to find out quickly.

Code:

static void rotateMatMethod3(int[][] mat, boolean isClockwise) {
    int n = mat.length;
    for (int layer = 0; layer < n/2; layer++) {
        for (int i = layer; i < n-1-layer; i++) {
            if (isClockwise) {
                int t = mat[layer][i];
                mat[layer][i] = mat[n - 1 - i][layer];
                mat[n - 1 - i][layer] = mat[n - 1 - layer][n - 1 - i];
                mat[n - 1 - layer][n - 1 - i] = mat[i][n - 1 - layer];
                mat[i][n - 1 - layer] = t;
            } else {
                int t = mat[layer][i];
                mat[layer][i] = mat[i][n - 1 - layer];
                mat[i][n - 1 - layer] = mat[n - 1 - layer][n - 1 - i];
                mat[n - 1 - layer][n - 1 - i] = mat[n - 1 - i][layer];
                mat[n - 1 - i][layer] = t;
            }
        }
    }
}
Approach 3:

This is my favourite and it's easy to remember and code. In this approach -

  1. At first make transpose of the matrix
  2. Reverse columns to rotate clockwise
  3. Reverse rows to rotate anti-clockwise
  • Complexity: 2 * O(N^2)
  • Space: O(1)
static void rotateMatMethod1(int[][] mat, boolean isClockwise) {
    int n = mat.length;
    // Make transpose
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int t = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = t;
        }
    }

    if (isClockwise) {
        // Rotate right
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int t = mat[i][j];
                mat[i][j] = mat[i][n - 1 - j];
                mat[i][n - 1 - j] = t;
            }
        }
    } else {
        // Rotate left
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int t = mat[i][j];
                mat[i][j] = mat[n - 1 - i][j];
                mat[n - 1 - i][j] = t;
            }
        }
    }
}

Full Code:

Blog Comments powered by Disqus.

Next Post Previous Post