Rotate Image (LeetCode 48)

The problem

You get a square n × n matrix. Rotate it 90° clockwise in place: you must change the given matrix, not build a second one and copy it back.

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

The first column read bottom-up (7, 4, 1) becomes the first row, and so on for every column.

How to think about it

Start with brute force. Make a new n × n grid and put each value where it belongs: cell (i, j) moves to (j, n-1-i). That is O(n²) time, which is fine, but it uses O(n²) extra space, and the problem forbids it. Writing the new values straight into the same grid without a copy fails too, because you overwrite cells you have not read yet.

The classic in-place answer rotates four cells at a time, layer by layer, using a temporary variable. It works, but the index juggling (matrix[n-1-j][i] and friends) is exactly where interview bugs live.

The key insight: a clockwise rotation is two simple moves combined. First transpose the matrix (swap (i, j) with (j, i), a mirror across the main diagonal). Then reverse each row (a mirror left to right). Follow one cell: (i, j) goes to (j, i) after the transpose, then to (j, n-1-i) after the reversal. That is exactly the rotation mapping. Both moves are easy to do in place, so the whole thing needs O(1) extra space.

Which pattern is this? In-place grid manipulation by index mapping. The tell is “rotate / flip / transpose a matrix, in place”. Write down where (i, j) must go, then look for simpler mirror moves that compose to it.

Approach

1. For every pair with j > i (cells above the diagonal), swap matrix[i][j] with matrix[j][i]. Starting j at i + 1 swaps each pair exactly once.
2. Reverse every row in place.
3. The matrix is now rotated 90° clockwise.

Solution

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):          # upper triangle only: each pair once
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()                      # mirror left-right
    return matrix
# rotate([[1,2,3],[4,5,6],[7,8,9]]) -> [[7,4,1],[8,5,2],[9,6,3]]

Dry run

On the 3 × 3 example:

Three swaps finish the transpose (the diagonal 1, 5, 9 never moves), and the row reversal gives the rotated matrix.

Complexity

• Time: O(n²). The transpose touches about n²/2 pairs, and reversing n rows of length n is n² more work. Every cell must move, so you cannot do better.
• Space: O(1) extra. Swaps and row.reverse() work in place.

Edge cases and pitfalls

• Swapping the whole matrix (j from 0 instead of i + 1) swaps every pair twice and undoes the transpose. This is the bug to watch for.
• Wrong order for the direction. Transpose + reverse rows is clockwise. For counter-clockwise, transpose then reverse each column (or reverse rows first, then transpose).
• 1 × 1 matrix is unchanged; both loops do nothing harmful.
• matrix = matrix[::-1]-style rebinding inside the function creates a new list and does not change the caller’s matrix. Mutate in place.
• Non-square matrices cannot be rotated in place; the problem guarantees n × n.

Related problems

• Spiral Matrix (LeetCode 54): also uses transpose + reverse, but to rotate the remaining grid as it is peeled.
• Set Matrix Zeroes (LeetCode 73): another in-place grid change where the order of writes matters.
• Game of Life (LeetCode 289): in-place grid update that avoids clobbering values you still need.