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.

Examples

Example 1:

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

Visual:
1 2 3      7 4 1
4 5 6  =>  8 5 2
7 8 9      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]]

Visual:
5  1  9  11      15 13 2  5
2  4  8  10  =>  14 3  4  1
13 3  6  7       12 6  8  9
15 14 12 16      16 7  10 11

Example 3:

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

Example 4:

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

Visual:
1 2      3 1
3 4  =>  4 2

Constraints

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

Solution Approach

There are two main approaches to rotate a matrix 90° clockwise in-place:

Approach 1: Layer-by-Layer Rotation (Recommended)

Key Insight: Rotate the matrix from the outermost layer to the innermost layer.

Think of the matrix as concentric squares (layers). For each layer:

1. Rotate groups of 4 cells at a time
2. Use a temp variable to perform 4-way swap
3. Pattern: Top ← Left ← Bottom ← Right ← Top

Algorithm:

For each layer (from 0 to n/2):
    For each cell in the layer (excluding corners to avoid double-processing):
        Save top cell
        Top ← Left
        Left ← Bottom
        Bottom ← Right
        Right ← Saved top

Why this works:

• For a 3×3 matrix: 1 layer (outer ring)
• For a 4×4 matrix: 2 layers (outer + inner)
• For a 5×5 matrix: 2 layers (outer + inner, center stays)
• Center element (for odd n) doesn't need rotation

Approach 2: Transpose + Reverse

Key Insight: 90° clockwise = Transpose + Reverse each row

Algorithm:

1. Transpose the matrix (swap matrix[i][j] with matrix[j][i])
2. Reverse each row

Example:

Original:        Transposed:      After Reversing Rows:
1 2 3            1 4 7            7 4 1
4 5 6    =>      2 5 8     =>     8 5 2
7 8 9            3 6 9            9 6 3

Why this works:

• Transpose swaps rows with columns
• Reversing each row completes the 90° rotation

Time & Space Complexity

Both Approaches:

• Time Complexity: O(n²)

  • We touch each of the n² cells exactly once

• Space Complexity: O(1)

  • In-place rotation, only using a few variables

Java Solution (Layer-by-Layer)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Rotate layer by layer
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;

            for (int i = first; i < last; i++) {
                int offset = i - first;

                // Save top
                int top = matrix[first][i];

                // Left -> Top
                matrix[first][i] = matrix[last - offset][first];

                // Bottom -> Left
                matrix[last - offset][first] = matrix[last][last - offset];

                // Right -> Bottom
                matrix[last][last - offset] = matrix[i][last];

                // Top -> Right
                matrix[i][last] = top;
            }
        }
    }
}

Python Solution (Layer-by-Layer)

def rotate(matrix: List[List[int]]) -> None:
    n = len(matrix)

    # Rotate layer by layer
    for layer in range(n // 2):
        first = layer
        last = n - 1 - layer

        for i in range(first, last):
            offset = i - first

            # Save top
            top = matrix[first][i]

            # Left -> Top
            matrix[first][i] = matrix[last - offset][first]

            # Bottom -> Left
            matrix[last - offset][first] = matrix[last][last - offset]

            # Right -> Bottom
            matrix[last][last - offset] = matrix[i][last]

            # Top -> Right
            matrix[i][last] = top

Java Solution (Transpose + Reverse)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 1. Transpose
        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;
            }
        }

        // 2. Reverse each row
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

Python Solution (Transpose + Reverse)

def rotate(matrix: List[List[int]]) -> None:
    n = len(matrix)

    # 1. Transpose
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # 2. Reverse each row
    for i in range(n):
        matrix[i].reverse()

Rotation Variations

90° Counter-Clockwise:

• Option 1: Transpose + Reverse each column
• Option 2: Reverse each column + Transpose

180° Rotation:

• Reverse each row + Reverse row order
• Or: Apply 90° clockwise twice

270° Clockwise (= 90° Counter-Clockwise):

• Apply 90° clockwise three times
• Or: Use counter-clockwise algorithm

Visual Understanding

For a 4×4 matrix, here's how layer-by-layer works:

Layer 0 (outer):
* * * *
*     *
*     *
* * * *

Layer 1 (inner):

  * *
  * *

Each layer is rotated independently, processing 4 cells at a time.

Related Problems

• Spiral Matrix (LeetCode 54): Traverse matrix in spiral order
• Spiral Matrix II (LeetCode 59): Generate spiral matrix
• Set Matrix Zeroes (LeetCode 73): Matrix manipulation
• Transpose Matrix (LeetCode 867): Simpler transpose operation
• Determine Whether Matrix Can Be Obtained By Rotation (LeetCode 1886): Check rotations

Pattern Recognition

This problem demonstrates:

• Matrix Manipulation pattern
• Layer-by-Layer Processing technique
• In-Place Algorithm (O(1) space)
• 4-Way Swap pattern
• Index Mathematics for rotation

Common Mistakes

1. ❌ Creating a new matrix (violates in-place requirement)
2. ❌ Incorrect index calculations for 4-way swap
3. ❌ Processing corners twice in layer approach
4. ❌ Wrong loop boundaries (< last not <= last)
5. ❌ Not using offset correctly in layer approach
6. ❌ Transposing incorrectly (using j = 0 instead of j = i + 1)

Tips for Interviews

• Clarify: Confirm it's 90° clockwise and in-place
• Visualize: Draw a small 3×3 example
• Explain: Mention both approaches (layer-by-layer and transpose+reverse)
• Choose: Layer-by-layer is more intuitive for rotation
• Edge Cases: Single element, 2×2 matrix, odd vs even size
• Test: Walk through the 4-way swap logic carefully
• Optimize: Both approaches are already optimal at O(n²) time, O(1) space

Complexity Comparison

| Approach | Time | Space | Code Complexity | Intuition | |----------|------|-------|-----------------|-----------| | Layer-by-Layer | O(n²) | O(1) | Medium | Harder to understand | | Transpose + Reverse | O(n²) | O(1) | Easy | Easier to remember |

Recommendation: Learn both! Transpose+Reverse is easier to code in an interview, but Layer-by-Layer shows deeper understanding of matrix manipulation.

Follow-Up Questions

1. Q: How would you rotate counter-clockwise?

   • A: Transpose + Reverse each column (or reverse columns + transpose)

2. Q: What if you can use extra space?

   • A: Could create new matrix, but doesn't improve time complexity

3. Q: How to check if a matrix is a rotation of another?

   • A: Rotate original and compare (LeetCode 1886)

4. Q: Can you do better than O(n²)?

   • A: No, must touch every cell at least once