1521. Rotate a Square In Place
An N by N grid is given. Turn it a quarter turn CLOCKWISE and print the
result, using no second grid: apart from a constant number of scalar variables,
the only storage allowed is the N * N cells the input arrived in.
1 2 3 -> 7 4 1
4 5 6 8 5 2
7 8 9 9 6 3
1 2 -> 3 1
3 4 4 2
7 -> 7
## Why this problem insists on a square
A quarter turn of an R by C grid has C rows and R columns. When
R and C differ, the answer simply does not FIT in the storage the input
occupies as a rectangle of the original shape, so "in place" is not a matter of
cleverness; it is impossible without reinterpreting the array. Problem 1522
does the reinterpreting version for a rectangle, and it is a different and
harder job. Here R == C, the shape is preserved, and a true in-place method
exists.
## What most people try first
Allocating the answer and filling it from the source. Correct, and it is
O(N^2) extra cells, which this problem forbids.
The next attempt is transpose then reverse each row, which IS in place for a
square and is a perfectly good answer. The version that fails is transposing
with both loops running over the full range: swapping g[i][j] with g[j][i]
for every i and j swaps each pair twice and leaves the grid unchanged. The
inner loop must start at i.
## Four cells at a time
for layer in 0 .. N/2 - 1:
for j in layer .. N-2-layer:
t = g[layer][j]
g[layer][j] = g[N-1-j][layer]
g[N-1-j][layer] = g[N-1-layer][N-1-j]
g[N-1-layer][N-1-j] = g[j][N-1-layer]
g[j][N-1-layer] = t
One temporary holds a single value, so the extra space is O(1).
## Why the cells form four-cycles
A quarter turn sends (a, b) to (b, N-1-a). Applying it four times returns
to (a, b), and it returns earlier only for a cell fixed by the turn, which
means a == b and b == N-1-a, so 2a == N-1. On an odd N that is the
single centre cell and on an even N there is none. Every other cell therefore
sits in a cycle of exactly four, and rotating the grid is rotating each of
those cycles by one.
## Why the inner loop stops one short
Layer layer of an N by N grid is a ring of side N - 2*layer, holding
4 * (N - 2*layer) - 4 cells, which is four cycles per starting column times
N - 1 - 2*layer columns. So the inner loop runs j from layer to
N - 2 - layer INCLUSIVE, one short of the far edge. Running it to
N - 1 - layer processes the corner twice and turns that ring by two steps
instead of one. On N = 5 the inner ring is where this first shows.
## The odd centre
When N is odd the centre cell is its own cycle and must be left alone. The
layer loop running to N/2 - 1 with integer division already excludes it: for
N = 5 the layers are 0 and 1, and the cell (2,2) is never touched.
## Overflow
Nothing is combined and values fit in a signed 32 bit integer, whose limit is
2147483647.
## Cost
O(N^2) time, each cell written exactly once, and O(1) extra memory.
Constraints - `1 ≤ N ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - the grid is square, which is what makes an in-place turn possible at all - no second grid may be allocated; `O(1)` extra memory beyond the input
Input
The first line contains one integer N.
Each of the next N lines contains N integers.
Output
Print the turned grid as N lines of N integers each, separated by single spaces. A quarter turn of a square keeps its shape.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.