Rotate Image

Problem

You are given a square grid of integers representing an image, n rows by n columns. Rotate the image 90 degrees clockwise in place: modify the given 2D list directly and do not allocate a second n x n grid.

• The grid is at most about 25 rows/columns on a side.
• Cell values are small integers, positive or negative.

Examples

• [[2,9,4],[7,5,3],[6,1,8]] → [[6,7,2],[1,5,9],[8,3,4]]. The left column 6,7,2 (read bottom to top) becomes the top row.
• [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] → [[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]].
• [[1]] → [[1]]; a 1x1 image is unchanged.

Hints

1. Where does the element at (r, c) end up after a clockwise quarter turn? Write the formula.
2. That mapping can be decomposed into two simpler operations, each of which is easy to do in place.
3. Transpose the matrix (swap (r, c) with (c, r)) and then reverse each row. Alternatively, rotate four elements at a time in cycles.