Matrix rotation algorithm

Question

This is the Matrix Rotation problem from hackerrank.com.

You are given a 2D matrix, \$a\,ドル of dimension ×ばつ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 ×ばつ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).

Matrix Rotation Visualization

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 - 4*i)*2 
 nbrOfRotations = R%loopLength
 for rotnIndex in range(nbrOfRotations):
 # Corner movements
 # Pivot
 refMat[i][i] = baseMat[i][i + 1]
 # Column End
 refMat[i][cLimit] = baseMat[i + 1][cLimit]
 # Row End
 refMat[rLimit][i] = baseMat[rLimit - 1][i]
 # Pivot diagonal
 refMat[rLimit][cLimit] = baseMat[rLimit][cLimit - 1]
 # Top movement
 for j in range(i+1, cLimit):
 refMat[i][j] = baseMat[i][j + 1]
 # Bottom movement
 for j in range(i+1, cLimit):
 refMat[rLimit][j] = baseMat[rLimit][j - 1]
 # Left movement
 for j in range(i+1, rLimit):
 refMat[j][i] = baseMat[j - 1][i]
 # Right movement
 for j in range(i+1, rLimit):
 refMat[j][cLimit] = baseMat[j + 1][cLimit]
 baseMat = deepcopy(refMat)
for i in refMat:
 for e in i:
 print(e, end = " ")
 print()

Note: No advanced libraries such as NumPy, SciPy etc. are allowed. However, I would love to know if they offer a better workaround.

• alexwlchan: It doesn’t seem that slow to me. Are there particular cases that are causing you problems?
• benSooraj: @alexwlchan, it does become slow when the inputs, for example, are of the dimension rows = 136, columns = 240 and rotations = 212131
• benSooraj: I was wondering if there is any way to pre-compute the new position of any element, instead of shifting them around. Or some other better/efficient way to get this done. Thanks for your inputs.
• spyr03: There isn't really a need to actually move the elements, just update the starting one for each layer, and all the rest just follow behind it. As an example, if you are rotating 1 2 3 4 you can just start later on (at 2) and print each answer from there
• spyr03: @BenSoorajM it may take a while to do the full code for me, I'll get back to you in a couple of days

Answer 1

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.

• SuperBiasedMan: Is c2’[i] a typo? It's not really correct syntax.
• Jan: It is pseudo syntax and means derived. This algorithm is not language specific and c2_derived I considered too long :) keeps you awake :P I also hope, that c1.length will be extracted in a local variable, that cN will be an array and so on...
• SuperBiasedMan: yes sorry I didn't follow it at first. I could tell it was partly psuedo code I just wasn't familiar with the derived notation in the middle of what's normal Python syntax otherwise (ie c1[i] is valid)
• holroy: How would you generate the original c1 and c2 array? Do you have a general formula for when the number of circles increases?
• Jan: I am not quite sure, what you are asking for. How to calculate the number of circles I wrote min(M,N)/2. The initial creation of c_n (can I use the math env in comments also?) looks trivial to me ;). Would you like to see the start of it?