1522. Transpose a Rectangle In Place

An R by C grid is given, stored as ONE array of R * C values in row-major order: the cell at row i, column j sits at flat position i * C + j.

Print its transpose, the C by R grid whose cell (j, i) holds the original (i, j), using no second array. Apart from a constant number of scalar variables the only storage allowed is that same array of R * C values, which afterwards is read as C rows of R.

1 2 3 flat 1 2 3 4 5 6 -> 1 4 4 5 6 2 5 flat 1 4 2 5 3 6 3 6

1 2 3 4 5 6 -> the same six values, read as six rows of one

## What most people try first

Swapping a[i*C + j] with a[j*C + i], the square recipe. On a rectangle j*C + i is not even the right position, and for j >= R it is not a cell of the transpose at all. On a 2 by 3 grid it reads position 2*3 + 0 = 6, which is outside the array.

The honest fallback is a second array, out[j*R + i] = a[i*C + j]. That is one clean pass and R * C extra cells, which this problem forbids.

The third attempt is a boolean "already moved" array. It is R * C bits, which is less, and it is still O(R C) extra.

## The transpose is one permutation of the flat array

Position p = i*C + j must end up at j*R + i. Let n = R*C. Because C * R is congruent to 1 modulo n - 1,

p * R mod (n - 1) = (i*C + j) * R mod (n-1) = i + j*R for 0 < p < n-1

so every position except the first and the last moves by multiplication by R modulo n - 1. Positions 0 and n - 1 are fixed.

Reading the permutation backwards, the value that must LAND at position p comes from position p * C mod (n - 1), since C is the inverse of R.

## Following cycles without a visited array

A permutation splits into cycles. Walking one cycle and carrying a value round it moves every element of that cycle with one temporary. The only difficulty is knowing which cycles are already done, and a visited array is what the constraint forbids.

The trick is the CYCLE LEADER test: process the cycle only from its smallest index. To check whether k is the smallest, walk the cycle from k and stop early if an index below k appears.

for k in 1 .. n-2: p = k * C mod (n-1); leader = true while p != k: if p < k: leader = false; break p = p * C mod (n-1) if not leader: continue cur = k; val = a[k] loop: nxt = cur * C mod (n-1) if nxt == k: a[cur] = val; break a[cur] = a[nxt]; cur = nxt

## Why the leader test is correct

Every cycle has exactly one smallest index, so each cycle is entered exactly once and every element is written exactly once. The test itself only reads positions, never writes, so a cycle that has already been rewritten is not misread: a rewritten cycle is never entered again, because its leader is below every other index in it and the loop only ever starts at the leader.

## The degenerate cases

When n is 1 or 2 the loop 1 .. n-2 is empty and there is nothing to do, which is right: a 1 by 1 grid and a 1 by 2 grid are already their own transposes as flat arrays. A single row or a single column is the same situation for any length, since every position is its own cycle. Those shapes also mean n - 1 can be 0, so the modulus must never be evaluated, and an empty loop is exactly what prevents that.

## Cost

The leader test walks a cycle of length L for each of its L members, so the worst case is O(n^2) when the permutation is a single long cycle, and R * C is capped at 2500 here for that reason. Memory is O(1) beyond the array.

## Overflow

p * C reaches 2500 * 50 = 125000, far inside a signed 32 bit integer whose limit is 2147483647. Values fit in 32 bits as well and nothing is added.

Constraints - `1 ≤ R ≤ 50` - `1 ≤ C ≤ 50` - `R * C ≤ 2500` - `-10^9 ≤ each value ≤ 10^9` - no second array may be allocated; `O(1)` extra memory beyond the input - `R` and `C` are independent; the grid need not be square