Rotate Image

• Difficulty: Medium
• Topics: Array, Math, Matrix
• Link: https://leetcode.com/problems/rotate-image/

Problem Description

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

Constraints:

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

Solution

1. Problem Deconstruction

Technical Definition:
Given an n×n 2D array matrix, perform an in-place 90-degree clockwise rotation. The transformation must satisfy:

$$\text{matrix}_{\text{new}}[i][j] = \text{matrix}_{\text{original}}[n-1-j][i] \quad \forall \ i,j \in [0, n-1]$$

Direct modification of the input matrix is required without allocating auxiliary 2D storage.

Beginner Explanation:
Imagine a square grid of numbers. Rotating it 90 degrees clockwise means:

• The top row becomes the last column.
• The second row becomes the second-last column.
• Continue this pattern until all rows are transformed into columns.
  Do this by moving numbers within the same grid without creating a copy.

Mathematical Formulation:
Let $M$ be the original matrix. The rotation is decomposed into two linear operations:

1. Transpose: $M^T[i][j] = M[j][i] \quad \forall \ i < j$ (swap elements across the main diagonal).
2. Row Reversal: $M_{\text{rotated}}[i][j] = M^T[i][n-1-j]$ (reverse the order of elements in each row).
   The composition yields:

$$M_{\text{rotated}}[i][j] = M[n-1-j][i]$$

which aligns with the 90-degree clockwise rotation.

Constraint Analysis:

• $n = \text{matrix.length} = \text{matrix}[i]\text{.length}$:
  • Limitation: Restricts solutions to square matrices; non-square rotations require dimension changes (invalid here).
  • Edge Case: $n=1$ leaves the matrix unchanged.
• $1 \leq n \leq 20$:
  • Limitation: Allows $O(n^2)$ solutions but mandates in-place operations.
  • Edge Case: Small $n$ avoids performance issues but requires handling odd/even layers.
• $-1000 \leq \text{matrix}[i][j] \leq 1000$:
  • Limitation: Values are integers; swaps don’t cause overflow.
  • Edge Case: Negative values don’t affect rotation logic.

---

2. Intuition Scaffolding

Real-World Metaphor:
Picture a group of people in a square dance formation. To rotate 90 degrees:

1. Transpose: Swap positions diagonally (person at $(i,j)$ moves to $(j,i)$).
2. Reverse Rows: Each row reverses its order (first and last in the row swap, etc.).

Gaming Analogy:
Like rotating a puzzle tile in Tetris:

• Flip the tile diagonally.
• Mirror the tile horizontally.
  The tile now faces clockwise without extra space.

Math Analogy:
Rotation is a composition of two reflections:

1. Reflect over the line $y = x$ (transpose).
2. Reflect over the line $x = \frac{n-1}{2}$ (row reversal).
   Each reflection is an involution; their composition yields rotation.

Common Pitfalls:

1. Double-Swapping in Transpose: Swapping all $(i,j)$ and $(j,i)$ without restricting to $i < j$ reverts changes.
2. Incorrect Reversal: Reversing columns instead of rows yields counter-clockwise rotation.
3. Layer Overwriting: In layer rotation, misindexing boundaries corrupts outer layers.
4. Extra Space: Using a new matrix violates in-place requirements.
5. Odd $n$ Center Handling: Skipping the center element in odd-sized matrices causes incorrect rotation.

---

3. Approach Encyclopedia

Approach 1: Transpose + Row Reversal

Pseudocode:

def rotate(matrix):  
    n = len(matrix)  
    # Transpose (swap upper triangle)  
    for i in range(n):  
        for j in range(i + 1, n):  
            swap(matrix[i][j], matrix[j][i])  
    # Reverse each row  
    for i in range(n):  
        left = 0  
        right = n - 1  
        while left < right:  
            swap(matrix[i][left], matrix[i][right])  
            left += 1  
            right -= 1  

Complexity Proof:

• Time: Transpose has $\binom{n}{2} = \frac{n(n-1)}{2}$ swaps. Row reversal has $n \cdot \frac{n}{2}$ swaps. Total: $O(n^2)$.
• Space: $O(1)$ (in-place swaps).

Visualization ($n=3$):

Original:    Transpose:    Reversed 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  

Approach 2: Vertical Reversal + Transpose

Pseudocode:

def rotate(matrix):  
    n = len(matrix)  
    # Reverse vertically (swap rows)  
    for i in range(n // 2):  
        swap(matrix[i], matrix[n - 1 - i])  
    # Transpose  
    for i in range(n):  
        for j in range(i + 1, n):  
            swap(matrix[i][j], matrix[j][i])  

Complexity Proof:

• Time: Vertical reversal: $\frac{n}{2}$ row swaps (each $O(n)$). Transpose: $\frac{n(n-1)}{2}$ swaps. Total: $O(n^2)$.
• Space: $O(1)$ (row swaps are pointer operations).

Visualization ($n=3$):

Original:    Vert Reversal:  Transpose:  
1 2 3        7 8 9          7 4 1  
4 5 6  →     4 5 6    →     8 5 2  
7 8 9        1 2 3          9 6 3  

Approach 3: Layer-by-Layer Rotation

Pseudocode:

def rotate(matrix):  
    n = len(matrix)  
    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  

Complexity Proof:

• Time: Processes $\frac{n}{2}$ layers. Each layer has $4(n-1-2\text{layer})$ assignments. Total: $O(n^2)$.
• Space: $O(1)$ (constant extra variables).

Visualization ($n=4$):

Layer 0: Swap 4-edge cycle  
Layer 1: Swap inner 2x2 cycle  

---

4. Code Deep Dive

Optimal Solution (Transpose + Row Reversal):

class Solution:  
    def rotate(self, matrix: List[List[int]]) -> None:  
        n = len(matrix)  
        # Transpose: swap upper triangle  
        for i in range(n):  
            for j in range(i + 1, n):  # Avoid diagonal and lower triangle  
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  
        # Reverse each row  
        for i in range(n):  
            left, right = 0, n - 1  
            while left < right:  
                matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left]  
                left += 1  
                right -= 1  

Line-by-Line Annotations:

1. n = len(matrix): Get matrix dimension.
2. Transpose Loop:
   • for i in range(n): Iterate rows.
   • for j in range(i + 1, n): Iterate columns $>i$ (upper triangle).
   • Swap: Exchanges (i, j) and (j, i); modifies in-place.
3. Row Reversal Loop:
   • for i in range(n): Process each row.
   • left, right: Pointers for reversal.
   • while left < right: Swap symmetrically until pointers meet.

Edge Case Handling:

• $n=1$: Loops exit immediately; matrix unchanged.
• $n=2$:
  • Transpose: Swaps (0,1) and (1,0) (e.g., [[1,2],[3,4]] → [[1,3],[2,4]]).
  • Row Reversal: [1,3] → [3,1], [2,4] → [4,2]; yields [[3,1],[4,2]].
• Odd $n$: Center element (matrix[n//2][n//2]) remains fixed during both steps.

---

5. Complexity War Room

Hardware-Aware Analysis:

• For $n=20$, total operations: $\frac{20 \times 19}{2} + 20 \times 10 = 190 + 200 = 390$ swaps.
• Memory: $20 \times 20 \times 4 \text{ bytes} = 1.6 \text{ KB}$ (fits in L1 cache).

Industry Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute Force (Copy)	$O(n^2)$	$O(n^2)$	★★★★★	❌ Violates in-place
Transpose + Reverse	$O(n^2)$	$O(1)$	★★★★☆	✅ Optimal & clear
Layer Rotation	$O(n^2)$	$O(1)$	★★★☆☆	✅ Demonstrates insight

---

6. Pro Mode Extras

Variants:

1. Counter-Clockwise Rotation:
   • Method 1: Transpose + Reverse columns.

     # After transpose:  
     for j in range(n):  
         top, bottom = 0, n - 1  
         while top < bottom:  
             swap(matrix[top][j], matrix[bottom][j])  
     

   • Method 2: Reverse rows + Transpose.
2. 180-Degree Rotation:
   • Reverse all rows → Reverse all columns, or apply 90° rotation twice.
3. Rectangular Matrix:
   • Requires new storage; rotate via $M_{\text{new}}[j][m-1-i] = M[i][j]$ for $m \times n$ input.

Interview Cheat Sheet:

• First Statement: “This is an $O(n^2)$ time, $O(1)$ space solution.”
• Key Insight: “90° rotation = transpose + row reversal.”
• Test Case: Verify with $n=2$ or $n=3$ immediately.
• Mention: “For odd $n$, the center is invariant.”
• Avoid: Allocating 2D arrays or diagonal double-swaps.