Rotate Image

def rotate(matrix):
    n = len(matrix)
    for i in range(n):             # transpose
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:             # reverse each row
        row.reverse()

Rotate Image. You're given a square grid of numbers, n by n, like the pixels of a picture. Turn it ninety degrees clockwise, in place, without building a second grid.

Take one through nine. After the turn, the rows read seven four one, eight five two, nine six three. The left column, read from the bottom up, became the top row.

The easy way copies each cell into a fresh grid, but that needs n squared extra space. Moving cells inside one grid is tricky, because every move overwrites a cell you still need.

The trick is two flips. First, transpose: mirror the grid across its diagonal, so rows become columns. Then reverse each row. Two flips make one quarter turn: a cell at row r, column c lands in row c, column n minus one minus r, exactly where a clockwise turn sends it.

In code, the first loop swaps every cell above the diagonal with its mirror below. Then each row is reversed. Only one value is held at a time.

Let's run it. Swap two and four, three and seven, six and eight. Now the rows read one four seven, two five eight, three six nine. Reverse each: seven four one, eight five two, nine six three. A four by four takes six swaps, same idea.

Each cell moves at most twice, so the time is n squared. Extra space is constant. Another way rotates four cells at a time, ring by ring, at the same cost.

Flip across, flip sideways, and the picture turns. That's Rotate Image.