Rotate Image

Allocate a new n x n matrix. For every source cell (r, c), write it directly to its rotated destination (c, n-1-r), then copy the new matrix back over the original (the problem’s in-place requirement is only there to push you toward the optimal solution — this version still runs correctly, just not for free).

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        rotated = [[0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                rotated[c][n - 1 - r] = matrix[r][c]
        matrix[:] = rotated

Correctness: the destination formula (c, n-1-r) is exactly the definition of a 90° clockwise rotation, so every cell lands in the right place in one pass. Complexity: every cell is visited once → O(n²) time, but a whole second matrix is kept alive at the same time as the original → O(n²) space.

Transpose the matrix in place by swapping matrix[r][c] with matrix[c][r] for every pair above the diagonal (each pair is swapped exactly once, so nothing gets overwritten before it is used). Then reverse each row. Composing the two: transposing sends (r, c) → (c, r), and reversing row c sends column index r to n-1-r, so the final position is (c, n-1-r) — the same destination as the rotation formula, achieved with only a constant number of temporary variables.

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        for row in matrix:
            row.reverse()

Watch the two passes compose: the transpose swaps each cell with its mirror across the diagonal, then reversing every row slides those new columns into their clockwise destinations, all in place.

Complexity: the transpose touches roughly n²/2 pairs and the row reversals touch every cell once more → O(n²) time, but only a few scalar temporaries are used → O(1) extra space.