Rotate Image (LC 48)

Pattern: Matrix transformation (transpose + reverse)
Difficulty: Medium
Key Concept: A 90° clockwise rotation equals transpose then reverse each row (for square matrices); alternatively rotate four cells in place in one loop.

Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees clockwise in-place.

Input: int[][] matrix
Output: void

---

1. Algorithm & Pseudocode

Brute force

Copy to new n×n array: new[c][n-1-r] = old[r][c]. O(n²) time, O(n²) space — violates in-place.

Optimal

Transpose + reverse rows

for r in 0..n-1:
  for c in r+1..n-1:
    swap matrix[r][c] with matrix[c][r]

for each row r:
  reverse row r

Four-way swap (single loop over upper-left quadrant):

for r in 0..n/2-1:
  for c in 0..(n+1)/2-1:
    tmp = matrix[r][c]
    matrix[r][c] = matrix[n-1-c][r]
    matrix[n-1-c][r] = matrix[n-1-r][n-1-c]
    matrix[n-1-r][n-1-c] = matrix[c][n-1-r]
    matrix[c][n-1-r] = tmp

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Transpose swaps across the main diagonal: (r,c) ↔ (c,r) — turns “vertical” structure into “horizontal” prep for a flip.
• Reverse each row after transpose completes the 90° clockwise mapping: (r,c) → (c, n-1-r) overall.
• Four-cycle method moves each corner of a rotating ring without extra storage beyond one temp — mathematically equivalent.

---

3. The Dry Run

1 2 3        transpose        1 4 7     reverse rows     7 4 1
4 5 6    =>                  2 5 8    =>              8 5 2
7 8 9                        3 6 9                      9 6 3

Step	matrix[0]	matrix[1]	matrix[2]
start	1,2,3	4,5,6	7,8,9
after transpose	1,4,7	2,5,8	3,6,9
after row reverse	7,4,1	8,5,2	9,6,3

---

4. Java Solution

Brute Force

class SolutionBrute {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] copy = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                copy[c][n - 1 - r] = matrix[r][c];
            }
        }
        for (int r = 0; r < n; r++) {
            System.arraycopy(copy[r], 0, matrix[r], 0, n);
        }
    }
}

Time: O(n²), Space: O(n²).

Optimal

Transpose + reverse

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int r = 0; r < n; r++) {
            for (int c = r + 1; c < n; c++) {
                int t = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = t;
            }
        }
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n / 2; c++) {
                int t = matrix[r][c];
                matrix[r][c] = matrix[r][n - 1 - c];
                matrix[r][n - 1 - c] = t;
            }
        }
    }
}

Four-way rotation

class SolutionFourWay {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int r = 0; r < n / 2; r++) {
            for (int c = 0; c < (n + 1) / 2; c++) {
                int t = matrix[r][c];
                matrix[r][c] = matrix[n - 1 - c][r];
                matrix[n - 1 - c][r] = matrix[n - 1 - r][n - 1 - c];
                matrix[n - 1 - r][n - 1 - c] = matrix[c][n - 1 - r];
                matrix[c][n - 1 - r] = t;
            }
        }
    }
}

Time: O(n²), Space: O(1).

---

5. The “Java vs. Others” Edge

• System.arraycopy only helps when copying whole rows from a buffer; in-place tricks avoid allocation entirely.
• Collections.reverse works on List, not int[]; manual swap loops are idiomatic.
• For rectangular rotate problems (different LC variant), transpose + reverse rules change — this problem is square only.

---

6. Complexity Summary

Approach	Time	Space	Notes
Extra matrix copy	O(n²)	O(n²)	Not in-place
Transpose + row reverse	O(n²)	O(1)	Easy to remember
Four-way swap	O(n²)	O(1)	No row reverse pass

---

ASCII: 90° clockwise on positions

Original positions of corners:

(0,0) (0,2)        After 90° CW:
                 (0,0) gets old (2,0)
(2,0) (2,2)      (0,2) gets old (0,0)
                 ... cycle of 4 corners