Rotate a Matrix by 90 Degrees (In Place), thesarfo

Rotate an n×n matrix clockwise. (LeetCode 48)

Brute force: map each input[i][j] directly to output[j][n-1-i] in a new matrix — O(n²) time, O(n²) extra space.

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][n - 1 - i] = matrix[i][j];
            }
        }
        return ans;
    }
}

Optimal — transpose, then reverse each row, in place: transposing swaps (i,j) with (j,i) (rows become columns), and diagonal elements stay put. Reversing every row afterward completes the 90° clockwise rotation.

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

    // Step 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;
        }
    }

    // Step 2: Reverse each row
    for (int i = 0; i < n; i++) {
        reverseRow(matrix[i]);
    }
}

private void reverseRow(int[] row) {
    int start = 0;
    int end = row.length - 1;
    while (start < end) {
        int temp = row[start];
        row[start] = row[end];
        row[end] = temp;
        start++;
        end--;
    }
}

Time: O(n²), no extra space beyond the swap variable.