Solutions

# Reverse and transpose, or layered 4-cell rotation.
# math

# Reverse rows and then transpose
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # 1. reverse the matrix rows
    matrix.reverse()

    # 2. transpose the matrix (rows become cols and viceversa)
    for r in range(n):
        for c in range(r, n):
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

    
# Brute force: O(n^2) space
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    rotated = [[0] * n for _ in range(n)]

    # 1. create rotated copy
    for r in range(n):
        for c in range(n):
            # NB: r=c, c=n-1-r
            rotated[c][n -1 -r] = matrix[r][c]

    # 2. copy back the rotated into the original
    for r in range(n):
        for c in range(n):
            matrix[r][c] = rotated[r][c]

    
# Layered 4-cell rotation
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    l, r = 0, n-1

    while l < r:
        # process current layer

        for i in range(r - l):
            top, bottom = l, r

            # save the top 
            topleft = matrix[top][l + i]

            # bottom left -> top left
            matrix[top][l + i] = matrix[bottom - i][l]

            # bottom right -> bottom left
            matrix[bottom - i][l] = matrix[bottom][r -i]

            # top right -> bottom right
            matrix[bottom][r - i] = matrix[top + i][r]

            # top left -> top right
            matrix[top + i][r] = topleft

        l += 1
        r -= 1