Rotate Image

The hard part of rotating a matrix is not visualizing the turn. It is moving every value without destroying one that has not moved yet.

The reliable Rotate Image solution is:

1. Transpose the square matrix across its main diagonal.
2. Reverse every row.

That composition performs a 90-degree clockwise rotation in place, using only pairwise swaps.

Read the Contract and Spot the Pattern

The task has four constraints that determine the solution:

• The matrix is square: n × n.
• The rotation is 90 degrees clockwise.
• The input matrix must be modified directly.
• You cannot allocate another n × n matrix for the result.

The values themselves do not help. They might be repeated, negative, or completely arbitrary. Correctness comes entirely from moving each value to the right coordinate.

Using zero-based indices, a value at (i, j) must move to:

(i, j) → (j, n - 1 - i)

For example, the top-left value (0, 0) must reach (0, n - 1), the top-right value must reach the bottom-right, and so on.

That coordinate rule is the anchor for the entire derivation. If your implementation produces a visually plausible result but violates this mapping, it is solving a different transformation.

The square shape matters too. Transposition exchanges (i, j) with (j, i). Those coordinates are valid partners only because the number of rows and columns is the same.

The Answer Direction: Transpose, Then Reverse Rows

Start with this matrix:

1 2 3
4 5 6
7 8 9

After transposing across the main diagonal:

1 4 7
2 5 8
3 6 9

Now reverse each row:

7 4 1
8 5 2
9 6 3

That final state is the matrix rotated 90 degrees clockwise.

Transpose exchanges row and column positions. It gets the values into the correct column structure, but their horizontal orientation is still backward. Reversing each row fixes that orientation.

The exact operation matters:

• Reverse each row: swap left and right elements within every row.
• Reverse the order of rows: move the top row to the bottom and the bottom row to the top.

Those are different transformations. Confusing them commonly produces a counterclockwise rotation or a reflection.

The two-pass method touches every matrix position a constant number of times:

• Time: O(n²)
• Auxiliary space: O(1)

The input matrix is mutable working storage. It is not counted as additional space.

Derive the Coordinate Movement

Do not memorize “transpose, then reverse rows” as a visual trick. Derive it from the destination coordinate.

Take an element at position (i, j).

Step 1: Transpose

Transposition swaps the row and column:

(i, j) → (j, i)

Step 2: Reverse the transposed row

After transposition, the element is in row j. Reversing that row changes its column from i to n - 1 - i:

(j, i) → (j, n - 1 - i)

Combine the two steps:

(i, j) → (j, i) → (j, n - 1 - i)

That is exactly the required clockwise destination.

A useful orientation check is to track one corner. The original top-left element must finish at the top-right. If it finishes at the bottom-left, your operation order or reflection direction is wrong.

This derivation also dictates the loop bounds.

For the transpose, (i, j) and (j, i) form one unordered pair. Process only one side of the diagonal so each pair is exchanged once.

For row reversal, positions j and n - 1 - j form a mirrored pair. Process only the first half of each row.

The loops are not arbitrary implementation details. They encode the proof that no pair is missed or swapped twice.

Use the Constraint to Reject the Obvious Baseline

The simplest correct algorithm ignores the in-place restriction:

result[j][n - 1 - i] = matrix[i][j]

For every source coordinate (i, j), write its value to the destination coordinate in a new matrix. This is an excellent mental correctness baseline because it follows the mapping directly.

But it allocates another n × n matrix, so it violates the contract.

Trying to write directly into the destination positions of the original matrix introduces an overwrite hazard. Suppose you move one value into its final position. That destination may still contain a value that must later move somewhere else. Without saving and coordinating an entire cycle, the original value disappears.

Transpose and row reversal avoid that global overwrite problem by decomposing the transformation into local swaps:

• Transpose swaps symmetric off-diagonal pairs.
• Row reversal swaps horizontally mirrored pairs.
• Each swap needs one temporary value, supplied by the language's assignment operation.

This is the key in-place pattern: replace a global rearrangement with a sequence of pairwise exchanges whose coverage you can prove.

Implement Both Passes Without Double-Swapping

The transpose should only inspect the cells above the main diagonal:

for i in range(n):
    for j in range(i + 1, n):
        swap(matrix[i][j], matrix[j][i])

Why start j at i + 1?

• The diagonal cells (i, i) already match their transposed positions.
• Starting at j = 0 would visit both (i, j) and (j, i).
• Swapping the same pair twice would undo the first swap.

Then reverse each row by exchanging positions from the two ends:

for j in range(n // 2):
    swap(matrix[i][j], matrix[i][n - 1 - j])

The n // 2 bound handles both parity cases. For an odd-length row, the center element has no partner and should remain where it is. For an even-length row, the two middle elements are still a mirrored pair and are included.

Here is the complete Python implementation:

def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # Transpose across the main diagonal.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row.
    for row in matrix:
        for j in range(n // 2):
            row[j], row[n - 1 - j] = row[n - 1 - j], row[j]

The function mutates matrix directly. It does not need to return a replacement matrix; the implicit None return is enough.

The state variables each have a specific obligation:

• n defines the valid coordinate range and mirror position.
• i selects a row and, during transposition, the diagonal anchor.
• j selects either an unprocessed transpose partner or a mirrored row partner.
• n - 1 - j is the matching position from the opposite side of the row.

I prefer keeping the two passes separate in an interview. A clever combined loop makes the code harder to inspect, while separate passes let you print the intermediate transposed matrix and isolate an orientation bug quickly.

Dry-Run Odd and Even Dimensions

A 3 × 3 matrix is useful because it exposes the center behavior:

1 2 3
4 5 6
7 8 9

During transposition, the algorithm swaps:

(0, 1) ↔ (1, 0)
(0, 2) ↔ (2, 0)
(1, 2) ↔ (2, 1)

It never swaps the diagonal:

(0, 0), (1, 1), (2, 2)

The center value 5 remains fixed throughout the entire rotation. That is correct: the center of an odd-sized square maps back to itself.

During row reversal, the algorithm swaps:

row 0: column 0 ↔ column 2
row 1: column 0 ↔ column 2
row 2: column 0 ↔ column 2

Column 1 is the center of each row and is untouched by the reversal pass.

Now consider an even-sized 4 × 4 matrix. There is no single center cell:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16

The transpose still processes only the upper triangle. The row reversal processes these column pairs:

0 ↔ 3
1 ↔ 2

Both central positions participate. No special branch is needed because n // 2 equals 2.

The important invariants are:

After processing transpose row i, every visited pair (i, j) and (j, i) has been exchanged exactly once, and no completed pair will be revisited.

During row reversal, every processed pair (j, n - 1 - j) is in its final left-to-right order.

The smallest valid input, a 1 × 1 matrix, also works naturally. The transpose loop has no off-diagonal pair, and range(1 // 2) is empty. The sole value stays in place.

Prove It, Measure It, and Catch the Mistakes

The correctness proof can be stated as one coordinate chain.

For any value initially at (i, j):

1. Transpose moves it to (j, i).
2. Reversing row j moves it to (j, n - 1 - i).
3. (j, n - 1 - i) is the required position for a 90-degree clockwise rotation.

Therefore every value reaches its correct destination.

The pairwise swaps preserve values because each swap exchanges two existing entries. No value is copied into multiple locations, and no value is discarded. The loop bounds ensure each required pair is handled once.

The complexity follows from the actual work:

• The transpose visits roughly half of the n² positions.
• The row-reversal pass visits roughly half of the positions again.
• Together, the passes take O(n²) time.
• The implementation stores only loop variables and temporary swap state, so auxiliary space is O(1).

Watch for these failure modes:

• Reversing columns instead of rows. This changes the orientation and can produce the wrong rotation.
• Using j = 0 during transpose. Every off-diagonal pair is swapped twice and returns to its original arrangement.
• Swapping the diagonal. It is harmless if swapped with itself, but it signals that the pair coverage has not been reasoned through.
• Reversing a full row without stopping halfway. The first half swaps with the second half, then those pairs are swapped back.
• Allocating a second matrix. The result may be correct, but the in-place contract is violated.
• Implementing the opposite rotation. Check the original top-left value: for clockwise rotation, it must land at the top-right.
• Assuming odd and even dimensions need separate algorithms. Correct pair bounds handle both.

A compact validation set catches most indexing errors:

1 × 1: confirms the empty-loop behavior
2 × 2 with distinct values: exposes pair-direction mistakes
3 × 3 numbered values: exposes clockwise/counterclockwise confusion
4 × 4 values: confirms even-dimension middle-pair handling

For the 3 × 3 numbered matrix, the expected result is:

7 4 1
8 5 2
9 6 3

The durable interview pattern is simple:

1. Derive the destination coordinate.
2. Look for in-place reflections, transposes, or reversals that compose into that mapping.
3. Turn each operation into pairwise swaps.
4. Prove every pair is visited exactly once.
5. Test one odd dimension and one even dimension.

When extra storage is forbidden, do not jump straight to complicated four-way cycles. First ask whether the coordinate transformation can be factored into simpler in-place operations. Here, the matrix turns cleanly through two moves: transpose, then reverse each row. Theory tells you why. The intermediate matrix tells you whether you implemented it correctly.