Efficient way to rotate a 2D array of integers of n size in Python

Question

I want to rotate (anti-clockwise) a 2D nxn array of integers and the 2D array is stored as a list of lists.

For example:

a = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]

After rotation, the output should look like:

b = [[3, 6, 9],
     [2, 5, 8],
     [1, 4, 7]]

I have written a function which performs the above rotation:

def rotate_clockwise(matrix):
    transposed_matrix = zip(*matrix) # transpose the matrix
    return list(map(list, reversed(transposed_matrix))) # reverse the transposed matrix

The function works well and the code looks pretty Pythonic to me. However, I am having trouble understanding the space and time complexity of my solution.

Can someone explain both the complexities of the constructs I have used, namely zip(*matrix), reversed(list), map(list, iterator) and list(iterator)?

How can I make this code more efficient? Also, what would be the most efficient way to rotate a 2D matrix?

NOTE: As mentioned by @Colonder in the comments, there might be a similar question to this. However, this question focuses more on discussing the space and time complexities of the problem.

Possible duplicate of [Rotating a two-dimensional array in Python](https://stackoverflow.com/questions/8421337/rotating-a-two-dimensional-array-in-python) — Colonder, Sep 13 '17 at 09:14
@Colonder I have read that thread and there are no references to efficiency or discussion on complexities. — Kshitij Saraogi, Sep 13 '17 at 09:16
If you're ok with using numpy, I believe the [numpy.rot90](https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.rot90.html) does what you're looking for. — Aaron N. Brock, Sep 13 '17 at 09:16
@AaronN.Brock No, I can't even if I so want to! I have to use standard library features only. — Kshitij Saraogi, Sep 13 '17 at 09:20

Willem Van Onsem · Answer 1 · 2017-09-13T09:27:05.743

The most efficient is probably using numpy for this:

>>> import numpy as np
>>> na = np.array(a)
>>> np.rot90(na)
array([[3, 6, 9],
       [2, 5, 8],
       [1, 4, 7]])

About the efficiency of your current approach. If the matrix is an n×n-matrix, then zip will work in O(n²), reversed will here work in O(n) (since it does this in a shallow way), the list function will work in O(n), but we do this n times since it is done in a map(..), so map(list,..) will work in O(n²). Finally the outer list will again work in O(n). There is however no way to rotate explicitly in less than O(n²), since we need to move O(n²) items.

In terms of space complexity zip, map, etc. work in an iterative way. But reversed will force the fact that zip will be fully enumerated. Each tuple from zip requires O(n), so the total amount of memory allocated will be O(n²). Next the map(list,..) works again iteratively, and each tuple will be converted to a list, that requires again O(n). We do this n times. So it will produce O(n²) memory complexity.

In numpy, if you do not rotate inplace, this will require O(n²) as well: this is a lower bound, since the new matrix will require O(n²) memory. If you do however rotate inplace, the memory compexity can be reduced to O(1).

Can we perform the rotation **inplace** without using numpy? — Kshitij Saraogi, Sep 13 '17 at 09:34
@KshitijSaraogi It can be done in place in a brute force-ish way — Abhay Nayak, Nov 06 '22 at 11:21

Abhay Nayak · Answer 2 · 2022-11-06T13:21:41.840

I might be late but if it helps, this is w.r.t python3.x

Can someone explain both the complexities of the constructs I have used, namely zip(*matrix), reversed(list), map(list, iterator) and list(iterator)?

zip() -> O(1) time and space, it returns the iterators of zip object something like <zip object at 0x104f18480>. But in your case, you've to convert it to a list access the items, which makes it O(n) time and space.
reversed() -> return iterators of list object <list_reverseiterator object at 0x100ffd1c0> and takes O(n/2) = O(n) time and O(n) space
list() -> iterates over n items and stores n items so O(n) time and space
map() -> iterates over m items n times so O(n*m) time and O(n+m) space.

So your code will run in O(n*m) time and O(n+m) space.

def rotate_clockwise(matrix):
    transposed_matrix = list(zip(*matrix)) # O(n) and O(n)
    return list(map(list, reversed(transposed_matrix))) # O(m*m) and O(n+m)

You could also use something like

def rotate_clockwise(matrix):
   return [list(element) for element in zip(*reversed(matrix))]

def rotate_anticlockwise(matrix):
   return [list(element) for element in reversed(zip(*(matrix)))]

or shallow copy (inefficient for larger inputs)

def rotate_clockwise(self, matrix):
    return [list(x) for x in zip(*matrix[::-1])]

def rotate_anticlockwise(self, matrix):
    return [list(x) for x in zip(*matrix)[::-1]]

All of these are very pythonic ways of approaching the question, however these do take extra space which should be alright for most cases. However, from a interview perspective as per your comment for in-place, you could try something like

def transpose(self, mat):
    rows = len(mat)
    cols = len(mat[0])
        
    for row in range(rows):
        for col in range(row+1, cols):
            mat[row][col], mat[col][row] = mat[col][row], mat[row][col]
    
def flip(self, mat):
    for row in mat:
        l,r = 0, len(row) - 1
        while l < r:
            row[l], row[r] = row[r], row[l]
            l += 1
            r -= 1

# Clockwise  - call transpose then flip
# Anti-clock - call flip then transpose

If this is for your work, go with pythonic code. In most cases using in-built functions or imported libraries are way better than writing up your own solutions because they are optimised with cPython and are generally faster for all scenarios which can't be achieved with your own solution. Saves a lot of time and efforts.

Efficient way to rotate a 2D array of integers of n size in Python

2 Answers2