# LeetCode — Rotate Image

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

Problem statement taken from: [https://leetcode.com/problems/rotate-image](https://leetcode.com/problems/rotate-image)

**Example 1:**

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

**Example 2:**

```
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
```

### Explanation

#### Rotate Groups of Four Cells

The first solution we can think of is to rotate the four corners of the matrix. We repeat this of the subsequent cells too.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1638200630568/N7mfd5lVh.png)

(Taken from LeetCode)

Let’s check the algorithm.

```
- initialize m = matrix.size, tmp
```

```
- loop for i = 0; i < m / 2; i++  
    - loop for j = i; j < m - 1 - i; j++  
      - tmp = matrix[i][j]  
      - matrix[i][j] = matrix[m - 1 - j][i]  
      - matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]  
      - matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]  
      - matrix[j][m - 1 - i] = tmp
```

The time complexity of the program is **O(M)** as each cell is getting read once and written once. Space complexity is **O(1)** because we do not use any other additional data structures.

**C++ solution**

```
class Solution {  
public:  
    void rotate(vector<vector<int>>& matrix) {  
        int m = matrix.size(), tmp;  
        int j = 0;  
  
        for(int i = 0; i < m/2; i++){  
            for(int j = i; j < m - 1 - i; j++){  
                tmp = matrix[i][j];  
                matrix[i][j] = matrix[m - 1 - j][i];  
                matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];  
                matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];  
                matrix[j][m - 1 - i] = tmp;  
            }  
        }  
    }  
};
```

**Golang solution**

```
func rotate(matrix [][]int)  {  
    m := len(matrix)  
    tmp := 0  
  
    for i := 0; i < m / 2; i++ {  
        for j := i; j < m - 1 - i; j++ {  
            tmp = matrix[i][j];  
            matrix[i][j] = matrix[m - 1 - j][i];  
            matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];  
            matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];  
            matrix[j][m - 1 - i] = tmp;  
        }  
    }  
}
```

**Javascript solution**

```
var rotate = function(matrix) {  
    let m = matrix.length;  
    let tmp = 0;  
    let i, j;  
  
    for(i = 0; i < m/2; i++){  
        for(j = i; j < m - 1 - i; j++){  
            tmp = matrix[i][j];  
            matrix[i][j] = matrix[m - 1 - j][i];  
            matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];  
            matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];  
            matrix[j][m - 1 - i] = tmp;  
        }  
    }  
};
```

Let’s dry-run our algorithm to see how the solution works.

```
Input:  
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]  
  
Step 1: m = matrix.length  
        m = 3  
  
Step 2: tmp = 0  
  
Step 3: loop i = 0; i < 3/2  
        0 < 3/2  
        0 < 1  
        true  
  
        j = i; j < 3 - 1 - 0  
        0 < 2  
        true  
  
        tmp = matrix[i][j]  
        tmp = 1  
  
        matrix[i][j] = matrix[m - 1 - j][i]  
        matrix[0][0] = matrix[3 - 1 - 0][0]  
        matrix[0][0] = matrix[2][0]  
        matrix[0][0] = 7  
  
        matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]  
        matrix[3 - 1 - 0][0] = matrix[3 - 1 - 0][3 - 1 - 0]  
        matrix[2][0] = matrix[2][2]  
        matrix[2][0] = 9  
  
        matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]  
        matrix[3 - 1 - 0][3 - 1 - 0] = matrix[0][3 - 1 - 0]  
        matrix[2][2] = matrix[0][2]  
        matrix[2][2] = 3  
  
        matrix[j][m - 1 - i] = tmp  
        matrix[0][3 - 1 - 0] = 1  
        matrix[0][2] = 1  
  
        j++  
        j = 1  
  
Step 4: j < 2  
        1 < 2  
        true  
  
        tmp = matrix[0][1]  
        tmp = 2  
  
        matrix[i][1] = matrix[m - 1 - j][i]  
        matrix[0][1] = matrix[3 - 1 - 1][0]  
        matrix[0][1] = matrix[1][0]  
        matrix[0][1] = 4  
  
        matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - 1]  
        matrix[3 - 1 - 1][0] = matrix[3 - 1 - 0][3 - 1 - 1]  
        matrix[1][0] = matrix[2][1]  
        matrix[1][0] = 8  
  
        matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]  
        matrix[3 - 1 - 0][3 - 1 - 1] = matrix[1][3 - 1 - 0]  
        matrix[2][1] = matrix[1][2]  
        matrix[2][1] = 6  
  
        matrix[1][m - 1 - i] = tmp  
        matrix[1][3 - 1 - 0] = 1  
        matrix[1][2] = 2  
  
        j++  
        j = 2  
  
Step 5: j < 2  
        2 < 2  
        false  
  
Step 6: i++  
        i = 1  
  
        1 < 3/2  
        1 < 1  
        false  
  
Output:  
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
```