Rotate Image

NeetCode: Rotate Image · LeetCode: 48. Rotate Image · Difficulty: Medium

You are given an n x n matrix of integers. Rotate it 90 degrees clockwise, in place.

Example

Text

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

Brute force: write into a second matrix

Look at where one cell lands. The cell at row i, column j moves to row j, column n - 1 - i: the first row becomes the last column. Allocate a fresh matrix, copy every cell to its new position, and store the new rows back into matrix. A Java int[][] is an array of row arrays, so the method assigns each new row to matrix[i]; the caller's variable still refers to the same outer array. The method returns void, as LeetCode requires.

Java

import java.util.Arrays;

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] out = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                out[j][n - 1 - i] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            matrix[i] = out[i];
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        new Solution().rotate(m);
        System.out.println(Arrays.deepToString(m));
        int[][] single = {{1}};
        new Solution().rotate(single);
        System.out.println(Arrays.deepToString(single));
    }
}

Output

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

Time: O(n²), which is optimal because every cell must be moved. Space: O(n²) for the copy, which the next version removes.

Optimal: transpose, then reverse each row

A clockwise rotation equals two simple moves. Transposing (swap m[i][j] with m[j][i]) mirrors the matrix over its main diagonal. Reversing each row then mirrors it left to right. Together they give the rotation, and both steps swap cells inside the same matrix.

step	matrix
start	`123 / 456 / 789`
transpose	`147 / 258 / 369`
reverse rows	`741 / 852 / 963`

When transposing, swap only the cells above the diagonal (j > i); otherwise every pair is swapped twice and the matrix is unchanged.

Java

import java.util.Arrays;

class Solution {
    public void 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 l = 0, r = n - 1; l < r; l++, r--) {
                int tmp = row[l];
                row[l] = row[r];
                row[r] = tmp;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        new Solution().rotate(m);
        System.out.println(Arrays.deepToString(m));
        int[][] single = {{1}};
        new Solution().rotate(single);
        System.out.println(Arrays.deepToString(single));
    }
}

Output

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

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