Rotating an NxN matrix

Question

I came up with the following solution for rotating an NxN matrix 90 degrees clockwise, to solve this CodeEval challenge:

Input

The first argument is a file that contains 2D N×N matrices (where 1 <= N <= 10), presented in a serialized form (starting from the upper-left element), one matrix per line. The elements of a matrix are separated by spaces.

For example:

a b c d e f g h i j k l m n o p

Output

Print to stdout matrices rotated 90° clockwise in a serialized form (same as in the input sample).

For example:

m i e a n j f b o k g c p l h d

It looks elegant to me, but can someone explain how its performance compares to the more common solutions mentioned here? Does it have \$O(n^2)\$ time complexity?

import sys, math

for line in open(sys.argv[1]):
    original = line.rstrip().replace(' ', '')
    nSquared = len(original)
    n = int(math.sqrt(nSquared))
    output = ''

    for i in range(nSquared):
        index = n * (n - 1 - i % n) + int(i / n)
        output += original[index] + ' '

    print(output.rstrip())

The expression n * (n - 1 - i % n) + int(i / n) is something I found while observing common patterns among rotated matrices.

Answer 1

1. The formula is elegant, and the approach is correct.

2. You have to be careful with complexities though. Specifically you have to be very clear about what \$n\$ is. Typically complexity is a function of the size of input (which is, provided that \$n\$ is a matrix dimension, \$n^2\$ itself), so I'd qualify your solution as linear. And since each element should be accounted for, no better solution is possible.

3. The asymptotic constant could be better. The problem doesn't ask to rotate the matrix; it is only asks to print the matrix as if it was rotated. In other words, building output is technically a waste of time. Use your formula to print elements as you enumerate them.

Answer 2

This solution is equivalent to the one in the accepted answer of the question you linked. The expression you used is the 1D-array equivalent of how that answer derived the appropriate (row, col) indexes in a 2D-array. The time complexity is \$O(N^2)\$, because in an NxN matrix there are \$N^2\$ cells, and your main operation visits all of them. You have some extra costs due to .rstrip() and .replace() but those don't change the asymptotic complexity.

In terms of Python coding, you forgot to close the file you opened after reading. You should wrap the loop inside a with open(...) as fh:, iterate over fh, and it will be automatically closed when leaving the with block.

Answer 3

I find the solution very complex.

I think you should first transform each line in a proper 2D array and then rotate it using the zip(*reversed(matrix)) before re-serializing the result.

How about this:

def rotate(data):
    size = int((len(data)/2)**0.5)+1
    matrix = [data.split(' ')[i:i+size] for i in range(0,size*size,size)]
    rotated_matrix = zip(*reversed(matrix))
    temp = [' '.join(row) for row in rotated_matrix]
    return ' '.join(temp)

data = 'a b c d e f g h i j k l m n o p'

rotate(data)

output - > 'm i e a n j f b o k g c p l h d'