Leetcode 48 : Rotate Image
Tags: java, programming, computerscience, algorithms
Published: 2021-11-25 14:06:01

## Problem Statement :

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.

## Test Cases : 

Example 1:

![Sample 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uojz6db9v2x0kmrxgchp.png)

 Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:


![Sample 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/50m60ovonwcvl46jesuo.png)
 
 
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Example 3:

Input: matrix = [[1]]
Output: [[1]]
Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

## Constraints:

* matrix.length == n

* matrix[i].length == n

* 1 <= n <= 20

* -1000 <= matrix[i][j] <= 1000

## Algorithm :

The simple idea is, consider this matrix
```
matrix = [[1,2,3],[4,5,6],[7,8,9]]
```

```
1 2 3
4 5 6
7 8 9

Just take the transpose and lets see what we got :

1 2 3           1 4 7
4 5 6.      =>  2 5 8   
7 8 9           3 6 9

So we got the above after doing the transpose operation.
```

```java
for (int i=0; i<row; i++) {
            for (int j=0; j<i; j++) {
                swap(matrix, i, j);
            }
        }
```

```
Now let's compare it with our possible answer.
Our transpose is :

1 4 7                            7 4 1
2 5 8.     and our answer is     8 5 2
3 6 9                            9 6 3

So what we observe, answer is just reversing each row after doing the transpose.

1 4 7. after reversing 7 4 1
2 5 8  after reversing 8 5 2
3 6 9  after reversing 9 6 3

which is what we needed as our answer.
```

So algorithm is pretty simple :

1) Take the transpose of the given matrix
2) Reverse each row

```txt
Note : The above is 90 degree clockwise direction. What if, we need to rotate 90 degree anti clockwise direction.

Same way, just take the transpose.

1 2 3           1 4 7
4 5 6.      =>  2 5 8   
7 8 9           3 6 9

Now what will be our possible answer if we do anti clockwise 90 degree rotation on given matrix.

1 2 3           3 6 9
4 5 6.      =>  2 5 8   
7 8 9           1 4 7

Now we can just observe the answer along with the transpose of the matrix

1 4 7                            3 6 9
2 5 8.     and our answer is     2 5 8
3 6 9                            1 4 7

So we can observe that if we just reverse all the column, we will get the desired output.

1 4 7. after reversing column wise 3 6 9
2 5 8                              2 5 8
3 6 9                              1 4 7
```

## Complexity : 

Time complexity is O(row * col) and since we are doing in-place, space complexity is O(1).

## Code : (Clockwise 90 degree rotation)

```java
class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i=0; i<row; i++) {
            for (int j=0; j<i; j++) {
                swap(matrix, i, j);
            }
        }
        for (int [] rowWise : matrix) {
            reverse(rowWise, 0, col - 1);
        }
    }
    
    private void swap(int [][] matrix, int i, int j) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
    
    private void reverse(int [] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}
```

## Github : 

{%github Rohithv07/LeetCode %}

{%github Rohithv07/LeetCodeTopInterviewQuestions %}