HackerRank ‘Matrix Rotation’ Solution

H
Short Problem Definition:

You are given a 2D matrix, a, of dimension MxN 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.

Link

[Algo] Matrix Rotation

Complexity:

time complexity is O(N×M)

space complexity is O(NxM)

Execution:

There is just lots of code, but the actual solution is pretty simple. I first extract layers, to simplify the logic. Then, I rotate the layers similarly to the Codility Rotation challenge.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def reverse(arr, i, j):
    for idx in xrange((j - i + 1) / 2):
        arr[i + idx], arr[j - idx] = arr[j - idx], arr[i + idx]
 
 
def rotateList(A, K):
    # performs a right rotation
    # K needs to be adjusted to len(A) - K for left rotation
    l = len(A)
    K %= len(A)
 
    reverse(A, l - K, l - 1)
    reverse(A, 0, l - K - 1)
    reverse(A, 0, l - 1)
 
    return A
 
 
def rotateLayers(N, M, R, layers):
    for layer in layers:
        rotateList(layer, len(layer) - R)
 
 
def rotateMatrix(M, N, R, mat):
    # generate a list of layers
    l = int(min(N, M) // 2)
    layers = [[] for _ in range(l)]
    for level in xrange(l):
        top = (N - 1) - 2 * level
        side = (M - 1) - 2 * level
        for i in range(top):  # right
            layers[level].append(mat[level][level + i])
        for j in range(side):  # down
            layers[level].append(mat[level + j][level + top])
        for i in range(top):  # left
            layers[level].append(mat[level + side][level + top - i])
        for j in range(side):  # up
            layers[level].append(mat[level + side - j][level])
 
    # rotate each layer
    rotateLayers(N, M, R, layers)
 
    # fill the layers back in
    for level in range(l):
        top = (N - 1) - 2 * level
        side = (M - 1) - 2 * level
        for i in xrange(top):
            mat[level][level + i] = layers[level].pop(0# right
        for j in range(side):
            mat[level + j][level + top] = layers[level].pop(0# down
        for i in range(top):
            mat[level + side][level + top - i] = layers[level].pop(0# left
        for j in range(side):
            mat[level + side - j][level] = layers[level].pop(0# up
 
 
def main():
    M, N, R = map(int, raw_input().split())
    mat = []
    for i in range(M):
        mat.append(list(map(int, raw_input().split())))
 
    rotateMatrix(M, N, R, mat)
 
    # print the rotated matrix
    for row in range(M):
        for col in range(N):
            print mat[row][col],
        print
 
 
if __name__ == '__main__':
    main()

About the author

Add comment

Archives

Categories