Conrad Bailey

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.