Rotate Image — Editorial

Opening the reading…

Intuitionwhy transpose followed by reversal turns rows into rotated columns

A 90-degree clockwise rotation sends the value at row i and column j to row j and column n - 1 - i. The destination changes both coordinates, so moving every value directly is awkward: several values may need to pass through the same temporary position unless you carefully rotate a cycle.

Transpose first by reflecting the matrix across its main diagonal. This changes the value at row i, column j into the position row j, column i. Each original column has now become a row, but its order is reversed relative to a clockwise rotation. Reversing every row supplies exactly that missing reversal, producing row j, column n - 1 - i.

The two in-place transformations compose into one clockwise rotation.

Approach

Read n from the square matrix so every coordinate has the same row and column range; the square shape is what lets one diagonal swap represent a complete transpose.

Walk only the cells above the main diagonal, where j starts at i + 1, and swap matrix[i][j] with matrix[j][i]; skipping the diagonal avoids pointless self-swaps, while visiting below it too would undo each exchange.

Reverse every row from its first element to its last; after transposition, this changes the original column order into the order required by a clockwise rotation.

Return without creating a second matrix, because all swaps and reversals modify the input storage directly and the problem requires an in-place result.

Complexitythe matrix is touched a constant number of times

MEASURE	BOUND	WHY
Time	O(n^2)	The upper triangle contains n(n - 1) / 2 entries and each row reversal examines n entries, so the total work is proportional to n^2; no cell is involved in more than a constant number of operations.
Space	O(1) extra	The swaps use only a constant number of temporary values, and the required output remains inside the input matrix, so it is excluded from working space. The bound stays O(1) even for the largest or any other shape allowed here.

Here n is the number of rows and also the number of columns in the square matrix.

Annotated solutionC++ · transpose then reverse · the shortest version to remember

CPPTranspose the upper triangle, then reverse each row in place.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

The lower bound j = i + 1 is the important placement detail. A transpose exchanges each off-diagonal pair exactly once, so the loop must stay on one side of the diagonal. Once that is done, reverse acts independently on each row and finishes the coordinate change without needing another matrix.

The four-way layer alternativea direct arrangement when you want the rotation visible in one pass

A direct rotation visits the matrix layer by layer, from the outside toward the center. For each position on the top edge, four cells form a cycle: top-left moves to top-right, top-right moves to bottom-right, bottom-right moves to bottom-left, and bottom-left moves to top-left. One temporary value lets you perform that cycle in place.

CPPRotate each ring with a four-way swap, without a separate transpose pass.

#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;

            for (int offset = 0; offset < last - first; offset++) {
                int top = matrix[first][first + offset];

                matrix[first][first + offset] =
                    matrix[last - offset][first];
                matrix[last - offset][first] =
                    matrix[last][last - offset];
                matrix[last][last - offset] =
                    matrix[first + offset][last];
                matrix[first + offset][last] = top;
            }
        }
    }
};

This is not an asymptotic optimisation: it still takes O(n^2) time and O(1) extra space. It is a different arrangement that exposes the movement of each value more directly. The transpose version is usually easier to verify, while the layer version is useful when you want the code to mirror the physical four-sided rotation.