1502. Fill a Rectangle in Spiral Order
No grid is given. Only R and C are. Build the R by C grid holding
1, 2, ... , R * C written in clockwise spiral order, starting at the top-left
cell and moving RIGHT, and print it.
R = 3, C = 4 1 2 3 4
-> 10 11 12 5
9 8 7 6
R = 4, C = 3 1 2 3
-> 10 11 4
9 12 5
8 7 6
R = 1, C = 6 -> 1 2 3 4 5 6
Note the second answer is not the transpose of the first. Transposing a clockwise spiral gives an ANTICLOCKWISE one.
## What most people try first
Stepping one cell at a time and turning right whenever the next cell is off
the grid or already written. That is correct, and it needs a second grid of
booleans to remember what has been written, which is R C extra cells for
information the boundaries already carry. At R = C = 1000 that is 10^6
extra entries and a membership test in the innermost loop.
The more expensive version of the same instinct keeps a LIST of written cells
and scans it before every step, which turns 10^6 cells into 10^12 pair
comparisons.
## Write, do not walk
This is problem 64 run backwards. There, the boundaries decide which value to read next; here they decide where to put the next value.
v = 1
while top <= bot and left <= right:
for j in left..right: g[top][j] = v++ then top++
for i in top..bot: g[i][right] = v++ then right--
if top <= bot: for j in right..left: g[bot][j] = v++ then bot--
if left <= right: for i in bot..top: g[i][left] = v++ then left++
## Why nothing is ever written twice
Each pass writes one full side and then retires that side's boundary, so the
live rectangle strictly shrinks. A cell is only reachable while it lies inside
the live rectangle, and it leaves that rectangle on the pass that writes it.
So the loop terminates after at most R + C passes and writes exactly
R * C cells.
## The two guards
Here the boundaries HAVE already moved when the bottom and left passes run, so
these guards are <= rather than the strict ones the ring-by-ring version
needs. Drop them and a single-row grid writes its row twice, the second time
in reverse, and the last value lands in the wrong place. R = 1, C = 6 is the
smallest case that shows it.
## Overflow
The largest value written is R * C, at most 10^6, which sits far inside a
signed 32 bit integer whose limit is 2147483647.
## Cost
O(R C) time and O(R C) for the answer, with no auxiliary structure at all.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - no grid is read; only `R` and `C` arrive - `R` and `C` are independent; the grid need not be square
Input
A single line containing two integers R and C.
Output
Print R lines of C integers each, separated by single spaces: the grid holding 1 to R * C in clockwise spiral order from the top-left cell.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.