# Matrix Rotation

#### 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: