# Rotate Image
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotate-image)
Canonical: https://scaleengineer.com/dsa/problems/rotate-image
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Matrix
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Mastercard](https://scaleengineer.com/companies/mastercard), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Roblox](https://scaleengineer.com/companies/roblox), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [Capital One](https://scaleengineer.com/companies/capital-one), [Netflix](https://scaleengineer.com/companies/netflix), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Rakuten](https://scaleengineer.com/companies/rakuten), [WatchGuard](https://scaleengineer.com/companies/watchguard)
---
## Problem
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**](https://en.wikipedia.org/wiki/In-place%5Falgorithm), which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

**Example 1:**

![](https://assets.glich.co/dsa/rotate-image/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/rotate-image/image1.jpg) 

**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]]

**Constraints:**

* `n == matrix.length == matrix[i].length`
* `1 <= n <= 20`
* `-1000 <= matrix[i][j] <= 1000`

# Approaches
## Using an Auxiliary Matrix
This is the most straightforward approach but it violates the in-place requirement of the problem. It involves creating a new matrix of the same dimensions to store the rotated image and then copying the result back to the original matrix.
**Time:** O(n^2) · **Space:** O(n^2)
**Pros:** Simple to understand and implement.; The logic for mapping coordinates is direct.
**Cons:** Violates the in-place constraint of the problem, making it an invalid solution for this specific problem statement.; High space complexity.
### Explanation
The core idea is to map each element `matrix[i][j]` from the original matrix to its new position `[j][n-1-i]` in the rotated matrix.

1.  We first declare a new `n x n` matrix, say `rotated`.
2.  We then iterate through the original `matrix` using nested loops. For each element `matrix[i][j]`, we calculate its new position and place it in the `rotated` matrix: `rotated[j][n-1-i] = matrix[i][j]`.
3.  After iterating through all elements, the `rotated` matrix will contain the 90-degree clockwise rotated image.
4.  Finally, we copy the contents of the `rotated` matrix back into the original `matrix` to satisfy the function signature, although this doesn't make the algorithm in-place.

```java
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][n - 1 - i] = matrix[i][j];
            }
        }
        // Copy the rotated matrix back to the original matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = rotated[i][j];
            }
        }
    }
}
```
### Algorithm
- Get the dimension `n` of the matrix.
- Create a new `n x n` integer matrix called `rotated`.
- Iterate through the original `matrix` with row index `i` from `0` to `n-1` and column index `j` from `0` to `n-1`.
- In each iteration, assign `matrix[i][j]` to `rotated[j][n-1-i]`.
- After the loops complete, iterate through both matrices and copy the elements from `rotated` back to `matrix`.

## In-place Rotation by Layers
This approach rotates the matrix in-place by considering it as a set of concentric layers or shells. We rotate one layer at a time, starting from the outermost layer and moving inwards.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Efficient in terms of space, satisfying the in-place requirement.; Performs the rotation in a single pass over the relevant elements.
**Cons:** The calculation of indices for the four-way swap can be tricky to get right and might be considered less intuitive than other in-place methods.
### Explanation
An `n x n` matrix has `floor(n/2)` concentric layers. We can process each layer independently.

For each layer, we iterate through its elements and perform a cyclic swap of four elements at a time. Consider an element at `matrix[row][col]`. In a 90-degree clockwise rotation, it moves to `matrix[col][n-1-row]`. This element, in turn, moves to `matrix[n-1-row][n-1-col]`, which moves to `matrix[n-1-col][row]`, and finally, this last element moves back to the starting position `matrix[row][col]`.

We can perform this 4-way swap using a single temporary variable. The outer loop iterates from the outermost layer (`layer = 0`) to the innermost one (`layer < n/2`). The inner loop iterates through the elements of the current layer, from the first element to the second-to-last element of a side (to avoid rotating corners multiple times).

```java
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                // Save the top element
                int temp = matrix[i][j];
                // Move left to top
                matrix[i][j] = matrix[n - 1 - j][i];
                // Move bottom to left
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                // Move right to bottom
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                // Move top to right
                matrix[j][n - 1 - i] = temp;
            }
        }
    }
}
```
### Algorithm
- Get the dimension `n` of the matrix.
- Iterate through the layers of the matrix. The outer loop runs from `i = 0` to `n/2 - 1`.
- For each layer `i`, iterate through its elements. The inner loop runs from `j = i` to `n - 1 - i - 1`.
- Inside the inner loop, perform a cyclic swap of four elements:
    - `top = matrix[i][j]`
    - `left = matrix[n-1-j][i]`
    - `bottom = matrix[n-1-i][n-1-j]`
    - `right = matrix[j][n-1-i]`
- Use a temporary variable to store one element (e.g., `top`) and move the other three elements in a cycle: `left -> top`, `bottom -> left`, `right -> bottom`, and finally `temp -> right`.

## Transpose and then Reverse
This is an elegant and efficient in-place approach that achieves the rotation by performing two simpler, sequential transformations: first transposing the matrix, and then reversing each row.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Very intuitive and easy to implement by breaking the problem into two standard matrix operations.; Code is clean and easy to read.; Satisfies the in-place O(1) space requirement.
**Cons:** Involves two passes over the data, which might be slightly less performant in theory than a single-pass approach, though the difference is usually negligible in practice.
### Explanation
A 90-degree clockwise rotation is mathematically equivalent to first transposing the matrix and then reversing each of its rows.

**Step 1: Transpose the matrix.** A transpose operation swaps `matrix[i][j]` with `matrix[j][i]`. To do this in-place, we can iterate through the upper triangle of the matrix (i.e., where `j > i`) and perform the swap.

**Step 2: Reverse each row.** After transposing, we iterate through each row of the modified matrix and reverse it. This can be done using a standard two-pointer technique for each row, swapping elements from the ends towards the center.

Combining these two steps results in the desired rotated matrix. This method is often preferred for its clarity and ease of implementation.

```java
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Step 1: Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}
```
### Algorithm
- Get the dimension `n` of the matrix.
- **Transpose the matrix:**
    - Iterate with `i` from `0` to `n-1`.
    - Iterate with `j` from `i+1` to `n-1`.
    - Swap `matrix[i][j]` with `matrix[j][i]`.
- **Reverse each row:**
    - Iterate with `i` from `0` to `n-1` (for each row).
    - Use two pointers, `left = 0` and `right = n-1`.
    - While `left < right`, swap `matrix[i][left]` with `matrix[i][right]`, then increment `left` and decrement `right`.

# Solutions
### CSharp

```csharp
public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        for (int i = 0; i < n >> 1; ++i) {
            for (int j = 0; j < n; ++j) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = t;
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
    }
}
```

### Java

```java
public class Rotate_Image { public class Solution { /* eg: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 */ public void rotate ( int [][] m ) { // m for matrix if ( m == null || m . length == 0 ) { return ; } // for each circle, start position is (i,i), length is rectangle size // eg. above: (0,0), length=5; (1,1), length=3 int i = 0 ; int length = m . length ; while ( i < m . length / 2 ) { int count = 0 ; while ( count < length - 1 ) { // @note: extra attention here "-1". // while (count < length) { int tmp = m [ i ][ i + count ]; // i+length-1: last index of this rectangle // i+length-1 - count: index from backward m [ i ][ i + count ] = m [ i + length - 1 - count ][ i ]; m [ i + length - 1 - count ][ i ] = m [ i + length - 1 ][ i + length - 1 - count ]; m [ i + length - 1 ][ i + length - 1 - count ] = m [ i + count ][ i + length - 1 ]; m [ i + count ][ i + length - 1 ] = tmp ; count ++; } length -= 2 ; // @note: shrink each edge length by 2 i ++; // start point moving along diagonal } } } // An Inplace function to rotate a N x N matrix by 90 degrees in anti-clockwise direction static void rotateMatrix_anticlock ( int N , int mat [][]) { // Consider all squares one by one for ( int x = 0 ; x < N / 2 ; x ++) { // Consider elements in group of 4 in // current square for ( int y = x ; y < N - x - 1 ; y ++) { // store current cell in temp variable int temp = mat [ x ][ y ]; // move values from right to top mat [ x ][ y ] = mat [ y ][ N - 1 - x ]; // move values from bottom to right mat [ y ][ N - 1 - x ] = mat [ N - 1 - x ][ N - 1 - y ]; // move values from left to bottom mat [ N - 1 - x ][ N - 1 - y ] = mat [ N - 1 - y ][ x ]; // assign temp to left mat [ N - 1 - y ][ x ] = temp ; } } } static void rotateMatrix_clockwise ( int N , int mat [][]) { // Consider all squares one by one for ( int x = 0 ; x < N / 2 ; x ++) { // Consider elements in group of 4 in // current square for ( int y = x ; y < N - x - 1 ; y ++) { // store current cell in temp variable int temp = mat [ x ][ y ]; // move values from right to top mat [ x ][ y ] = mat [ y ][ N - 1 - x ]; // move values from bottom to right mat [ y ][ N - 1 - x ] = mat [ N - 1 - x ][ N - 1 - y ]; // move values from left to bottom mat [ N - 1 - x ][ N - 1 - y ] = mat [ N - 1 - y ][ x ]; // assign temp to left mat [ N - 1 - y ][ x ] = temp ; } } } } ////// class Solution_diagonal { public void rotate ( int [][] matrix ) { transpose ( matrix ); reflect ( matrix ); } public void transpose ( int [][] matrix ) { int n = matrix . length ; for ( int i = 0 ; i < n ; i ++) { for ( int j = i ; j < n ; j ++) { int tmp = matrix [ j ][ i ]; matrix [ j ][ i ] = matrix [ i ][ j ]; matrix [ i ][ j ] = tmp ; } } } public void reflect ( int [][] matrix ) { int n = matrix . length ; for ( int i = 0 ; i < n ; i ++) { for ( int j = 0 ; j < n / 2 ; j ++) { int tmp = matrix [ i ][ j ]; matrix [ i ][ j ] = matrix [ i ][ n - j - 1 ]; matrix [ i ][ n - j - 1 ] = tmp ; } } } } ////// class Solution { public void rotate ( int [][] matrix ) { int s = 0 , n = matrix . length ; while ( s < ( n >> 1 )) { int e = n - s - 1 ; for ( int i = s ; i < e ; ++ i ) { int t = matrix [ i ][ e ]; matrix [ i ][ e ] = matrix [ s ][ i ]; matrix [ s ][ i ] = matrix [ n - i - 1 ][ s ]; matrix [ n - i - 1 ][ s ] = matrix [ e ][ n - i - 1 ]; matrix [ e ][ n - i - 1 ] = t ; } ++ s ; } } }
```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var rotate =
  function (matrix) {
    matrix.reverse();
    for (let i = 0; i < matrix.length; i++) {
      for (let j = 0; j < i; j++) {
        [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
      }
    }
  };

```

### Python

```python
class Solution (object):
    def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: void Do not return anything, modify matrix in-place instead. """ if len(matrix) == 0: return h = len(matrix) w = len(matrix[0]) for i in range(0, h):  # mirror for j in range ( 0 , w / 2 ): matrix [ i ][ j ], matrix [ i ][ w - j - 1 ] = matrix [ i ][ w - j - 1 ], matrix [ i ][ j ] for i in range ( 0 , h ): # transpos for j in range ( 0 , w - 1 - i ): matrix [ i ][ j ], matrix [ w - 1 - j ][ h - 1 - i ] = matrix [ w - 1 - j ][ h - 1 - i ], matrix [ i ][ j ] ############ class Solution : def rotate ( self , matrix : List [ List [ int ]]) -> None : n = len ( matrix ) for i in range ( n >> 1 ): for j in range ( n ): matrix [ i ][ j ], matrix [ n - i - 1 ][ j ] = matrix [ n - i - 1 ][ j ], matrix [ i ][ j ] for i in range ( n ): for j in range ( i ): matrix [ i ][ j ], matrix [ j ][ i ] = matrix [ j ][ i ], matrix [ i ][ j ]

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/rotate-image/ // Time: O(N^2) // Space: O(1) class Solution { public: void rotate ( vector < vector < int >>& A ) { int N = A . size (); for ( int i = 0 ; i < N / 2 ; ++ i ) { for ( int j = i ; j < N - i - 1 ; ++ j ) { int tmp = A [ i ][ j ]; A [ i ][ j ] = A [ N - j - 1 ][ i ]; A [ N - j - 1 ][ i ] = A [ N - i - 1 ][ N - j - 1 ]; A [ N - i - 1 ][ N - j - 1 ] = A [ j ][ N - i - 1 ]; A [ j ][ N - i - 1 ] = tmp ; } } } };
```