# Matrix Layer Rotations

This problem comes from HackerRank.

You can see my full solution in the GitHub repo.

## Problem Summary

Given a matrix and a number of rotations, print the result of that matrix being rotated counter-clockwise that many times.

## Insights

It has been a while since I took linear algebra, but thankfully it is not necessary to solve this problem efficiently. There are three important insights.

### Rings

Instead of thinking about the matrix holistically, think about it as
a series of concentric *rings*. In this perspective rotating the
matrix `r`

times is the same as rotating each ring `r`

times.

### Rotation == Swapping

Rotating a ring with `n`

elements **counter-clockwise** once is
equivalent to swapping some element of the ring **clockwise** `n-1`

times. Just try it out on a small example to gain the intuition
behind this idea.

`r`

Rotations == `r % n`

Rotations

If a ring has `n`

elements, then rotating the ring `n`

times brings
it back to the original position.

### Bonus: `r % n`

Counter-Clockwise Rotations == `n - (r % n)`

Clockwise Rotations

This is an optimization I did not implement, but it puts the upper
bound on swaps at `n/2`

as opposed to `n-1`

without. E.g. if a ring
has 100 elements, then clearly it's more efficient and equivalent
to perform 1 clockwise rotation than it is to do 99
counter-clockwise rotations.

## Implementation

The structure of my solution is like this in English

for each ring: calculate number of effective_rotations for i = 0...effective_rotations-1: swap along top row of ring, left to right swap along right column of ring, top to bottom swap along bottom row of ring, right to left swap along left column of ring, bottom to one below the top print the matrix

This is not hard to translate into code if you are disciplined in variable naming, though two lines bear explaining.

### Ring Counter

for (int i{0}; i < min(rows, cols) / 2; ++i) {

Rings require the same amount of columns as they do rows (2 of
each), so we run out of rings whenever we run out of one of the
two. Conveniently, `matrix[i][i]`

references the top left corner of
the `i-th`

ring.

### Effective Rotations

int effective_rotations{r % ((row_len*2) + (col_len*2) - 4)};

Earlier I referred to the number of elements in ring as `n`

; here
`n == ((row_len*2) + (col_len*2) - 4)`

. It's your basic
perimeter formula, but subtracting 4 is necessary to account for
the four corners where the rows and columns overlap.

## Final Complexity

There are `min(rows, cols) / 2`

rings, and for each ring the maximum
number of effective rotations is less than or equal to ```
(rows * 2) +
(cols * 2) - 4 - 1
```

. This gives `O(min(rows,cols)*(rows+cols))`

which is `O(min(rows,cols)*max(rows,cols))`

, which is simply
`O(rows*cols)`

. This bound could be tighter with a better expression
for the arithmetic series arising from the perimeters of rings, but
I'm no mathmetician.

This implementation passed all test cases.