class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(1)
    where, n is the side length. Every cell is touched exactly once.
    Pitfalls: range(r-l), not range(r-l+1). An edge holds r-l+1 cells but the corners are shared with the neighbouring edge, so the +1 version writes them twice and corrupts the ring. A 3x3 outer ring is 8 cells = 2 iterations x 4 moves.

    Read the editorial first, code included, then wrote it out. 11m is typing time, not a
    solve time, so this problem is still owed a cold re-solve.

    Rotate four cells at a time through a single temp, ring by ring, moving the l/r bounds
    inward. The assignments walk the cycle backwards (each slot pulls from the source that
    feeds it), so the code reads counter-clockwise while the net rotation is clockwise, which
    is the part that is easy to get inverted. t and b always equal l and r on a square matrix,
    they only exist so the four expressions read as top/bottom/left/right.

    Transpose the upper triangle then reverse each row is the other O(1) route: fewer indices
    to get wrong and faster to write under pressure, at the cost of looking like a memorised
    trick. Worth knowing both, this one is the answer when they want to see the index work.
    '''
    def rotate(self, matrix: List[List[int]]) -> None:
        l, r = 0, len(matrix)-1
        while l < r:
            t, b = l, r
            for i in range(r-l):
                temp = matrix[t][l+i]
                matrix[t][l+i] = matrix[b-i][l]
                matrix[b-i][l] = matrix[b][r-i]
                matrix[b][r-i] = matrix[t+i][r]
                matrix[t+i][r] = temp
            l += 1
            r -= 1

import copy
class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(n^2)
    where, n is the side length, so the work is linear in the n^2 cells.
    Pitfalls: copy.deepcopy is the wrong tool for a grid of ints, it recurses and memoises object ids. [row[:] for row in matrix] is identical here and measured 3x faster at n=20.
    Do not use in interview: The problem says in as many words not to allocate a second matrix, and this allocates one. That constraint is the whole reason 48 is a Medium and not an Easy, so answering with a deepcopy answers the Easy. LeetCode only diffs the final contents of `matrix` and accepts it; a human asks for the O(1) version on sight. Use [ring-rotate] instead.

    Solved unaided in 13m 18s. The mapping (r, c) -> (c, n-1-r) is the right transform and
    that part was mine, but writing into a copy dodges the constraint the problem is built
    around. Counts as the Easy half of the problem, not a solve. See [ring-rotate] below.
    '''
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        cp = copy.deepcopy(matrix)
        for r, row in enumerate(cp):
            for c, p in enumerate(row):
                matrix[c][n-1-r] = p