Matrix rotation algorithm

This is the Matrix Rotation problem from hackerrank.com.


You are given a 2D matrix, \$a\$, of dimension \$M×N\$ and a positive integer
\$R\$. You have to rotate the matrix R times and print the resultant
matrix. Rotation should be in anti-clockwise direction.


Rotation of a \$4×5\$ matrix is represented by the following figure. Note
that in one rotation, you have to shift elements by one step only
(refer sample tests for more clarity).





It is guaranteed that the minimum of \$M\$ and \$N\$ will be even.


Input


First line contains three space separated integers, \$M\$, \$N\$ and \$R\$, where \$M\$ is the number of rows, \$N\$ is number of columns in matrix, and \$R\$ is the number of times the matrix has to be rotated. Then \$M\$ lines follow, where each line contains \$N\$ space separated positive integers. These \$M\$ lines represent the matrix.


Output


Print the rotated matrix.


Constraints

• \$2 \le M, N \le 300\$

• \$1 \le R \le 10^9\$

• \$\min(M, N) ≡ 0 \pmod 2\$

• \$1 \le a_{ij} \le 10^8\$, where \$i \in [1\ldots M]\$ and \$j \in [1\ldots N]\$

Sample Input #00

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #00

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15

Sample Input #01

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #01

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Following is how I tried to solve the problem, but it runs just too slow:

```
from copy import deepcopy

aM, aN, R = map(int, input().split())

pivots = min(aM, aN)//2
refMat = []
baseMat = []

for i in range(aM):
readInput = list(map(int, input().split()))
baseMat.append(readInput)

refMat = deepcopy(baseMat)

for i in range(pivots):
cLimit = (aN - 1) - i
rLimit = (aM - 1) - i
loopLength = (aM + aN - 2 - 4i)2
nbrOfRotations = R%loopLength

for rotnIndex in range(nbrOfRotations):

# Corner movements
# P

Much better algorithm in my view:

Consider first matrix example

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15 16

R=rotations

convert in 2 circles (at least either M or N is even, thus there is no single center point):

c1 = [1,2,3,4,8,12,16,15,14,13,9,5]
c2 = [6,7,11,10]

for each position calculate actual value:

c1’[i] = c1[(i+R)%c1.length]
c2’[i] = c2[(i+R)%c2.length]
…

The number of circles is min(M, N)/2 hence this strange constraint in the task :)

This solves in linear \$O(M+N)\$ complexity rather than your cubic \$O(M\cdot N\cdot R)\$ complexity.

EDIT: of course revert the circles back to the matrix format.

StackExchange Code Review Q#98540, answer score: 8