Matrix rotation algorithm

Question

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 - 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.

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.