45. Rotate Image

A 90-degree clockwise rotation equals two simple in-place operations: transpose the matrix (swap across the main diagonal), then reverse each row. No extra matrix needed.

Idea

Rotating 90° clockwise sends element (i, j) to (j, n-1-i). That exact mapping is achieved by composing two easy in-place steps:

1. Transpose — reflect across the main diagonal: swap matrix[i][j] with matrix[j][i].
2. Reverse each row — reflect horizontally.

Together, transpose + horizontal flip = 90° clockwise rotation.

Algorithm

1. For i in 0..n-1, for j in i+1..n-1: swap matrix[i][j] and matrix[j][i].
2. For each row: reverse it.

Worked example: [[1,2,3],[4,5,6],[7,8,9]]

• Transpose → [[1,4,7],[2,5,8],[3,6,9]].
• Reverse each row → [[7,4,1],[8,5,2],[9,6,3]].

Complexity

• Time: O(n²).
• Space: O(1) — rotated in place.

class Solution {
    public int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        for (int[] row : matrix) {
            for (int lo = 0, hi = n - 1; lo < hi; lo++, hi--) {
                int tmp = row[lo];
                row[lo] = row[hi];
                row[hi] = tmp;
            }
        }
        return matrix;
    }
}