# Rotate Image

You are given an `n x n 2D` matrix representing an image. Rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example :

```Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

Rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]```

The following figure is a pictorial representation of the rotation process:

Transpose and then Reverse:

The obvious idea would be to transpose the matrix first and then reverse each row. This simple approach already demonstrates the best possible time complexity O(n2).

### Transpose of a Matrix

Transpose is a matrix formed by swapping the rows into columns and vice-versa. The new matrix obtained by interchanging the rows and columns of the original matrix is called the transpose of the matrix. If `A = [aij`] be an m × n matrix, then the matrix obtained by interchanging the rows and columns of A would be the transpose of A. of It is denoted by `A′ `or `(AT)`. In other words, if `A = [aij]mx`n ,then `A′ = [aji]nxm` . For example, check the following figure as a pictorial representation of transpose of a matrix.

Now to solve the problem we have to Transpose the matrix first and then reverse each row

### Java Code

```class MatrixSolution {

public void rotateMatrix(int[][] matrix) {
transpose(matrix);
System.out.println("Matrix After Transpose");
print(matrix);
reverse(matrix);
}

private void transpose(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix.length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}

private void reverse(int[][] matrix) {
for (int[] arr : matrix) {
for (int i = 0, j = matrix.length - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

public void print(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}

public class RotateMatrix {

public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
MatrixSolution matrixSolution = new MatrixSolution();
System.out.println("Matrix Before Rotation>>");
matrixSolution.print(matrix);
matrixSolution.rotateMatrix(matrix);
System.out.println("Matrix After 90 Degree Rotation>>");
matrixSolution.print(matrix);
}
}
```

The output of the program:

```Matrix Before Rotation:
1 2 3
4 5 6
7 8 9

Matrix After Transpose:
1 4 7
2 5 8
3 6 9

Matrix After 90 Degree Rotation:
7 4 1
8 5 2
9 6 3
```
• Time complexity: `O(N2)`.
• Space complexity: `O(1)` since we do a rotation in place

Categories: 2D Array