mediumArrays & Matrix (Must-Do)

Rotate Image (Matrix 90 deg)

Rotate a square matrix 90 degrees clockwise by changing the existing matrix. Do not allocate another matrix for the result.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated rows of a square matrix.

Expected result

The rotated matrix in the same format.

Case 1

Input

1 2
3 4

Expected output

3 1
4 2

Case 2

Input

Expected output

Case 3

Input

-1 0
2 -3

Expected output

2 -1
-3 0

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is a new matrix with matrix[j][n-1-i] ≥ ts matrix[i][j]. Correct, O(n^2) time and space. n ≤ 20 fits, but the problem requires in-place. The extra matrix is the bottleneck. A 90^\circ clockwise turn factors into two in-place flips: reverse upside-down, then transpose across the main diagonal. (i, j) goes to (n-1-i, j), then to (j, n-1-i) — the target. Two rounds of swaps, O(1) extra space.

According to the problem requirements, we need to rotate matrix[i][j] to matrix[j][n - i - 1].

We can first flip the matrix upside down, i.e., swap matrix[i][j] with matrix[n - i - 1][j], and then flip the matrix along the main diagonal, i.e., swap matrix[i][j] with matrix[j][i]. This way, we can rotate matrix[i][j] to matrix[j][n - i - 1].

The time complexity is O(n^2), where n is the side length of the matrix. The space complexity is O(1).

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.