Python 3 function to rotate an image 90°

Question

A coding challenge that rotates an image 90 degrees counterclockwise. The image is represented as an array matrix. I believe the time complexity is O(n²), but I'd like to know for sure, as well as any other feedback.

def rotate_image(img):
    rotated_image = [[] for x in range(len(img))]
    for i in range(len(img)):
        for j in range(len(img[i])):
          rotated_image[len(img) - j - 1].append(img[i][j])
    return rotated_image

Example usage:

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

rotated_img = rotate_image(image)
for i in rotated_img:
    print(i)

Outputs:

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

Answer 1

I believe the time complexity is \$O(n^2)\$, but I'd like to know for sure

There's a general method for figuring out the time complexity for a piece of code, which is to annotate each line with the count of times it executes, and the average time it takes to execute, and then multiply and add. Before we do this it helps to rewrite the code so that just one thing is happening on each line.

CODE                                   COUNT   TIME
=====================================  ======  ====
def rotate_image(img):                 
    n = len(img)                       1       t0
    indexes = range(n)                 1       t1
    rotated_image = []                 1       t2
    for _ in indexes:                  n       t3
        rotated_image.append([])       n       t4   (*)
    for i in indexes:                  n       t5
        for j in indexes:              n*n     t6
            k = n - j - 1              n*n     t7
            row = rotated_image[k]     n*n     t8
            entry = img[i][j]          n*n     t9
            row.append(entry)          n*n     t10  (*)
    return rotated_image               1       t11

Here \$t_0, t_1, \ldots, t_{11}\$ are constants giving the average time taken to execute each line of code (their exact values don't matter for the big-O analysis).

How do I know that these are all constants, and don't depend on \$n\$? Well, I used my knowledge about how Python is implemented, but in cases of doubt I consulted the Time Complexity page on the Python Wiki. This tells us, for example, that getting the length of a list takes \$O(1)\$ (and so \$t_0\$ is constant); that getting an item from a list takes \$O(1)\$ (and so \$t_8\$ and \$t_9\$ are constant). The two lines marked (*) have calls to list.append: the Time Complexity page tells us that these calls take amortized time \$O(1)\$. This means that the time taken by individual calls may vary, but on average it is constant.

So, adding all this up, the total time taken on input of size \$n×n\$ is $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ If \$n≥1\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.

Using the same method, we can get lower bounds too. For all \$n≥0\$, $$T(n) > n^2(t_6 + t_7 + t_8 + t_9 + t_{10})$$ and so \$T(n) = Ω(n^2)\$. Combining these two results, \$T(n) = Θ(n^2)\$.

(Once you get comfortable with using this method, the result in simple cases like this will be obvious, and so you can skip the detail, but it's useful to know that you can produce the detail if needed in more complex cases.)

Answer 2

You can use NumPy module that's good with arrays and matrices. It has a built-in for exactly that purpose -

import numpy as np

np.rot90(image).tolist()

With array manipulations, that's essentially same as performing matrix/array transpose and then flipping the rows -

np.asarray(image).T[::-1].tolist()

If the input is already an array, we can skip the array-conversion. Also, if the output as an array is okay, it would be simply a view into the input and as such the entire operation would be virtually-free.

Thus, with image_arr as the input array, it would be -

np.rot90(image_arr)

With transpose and flipping rows -

image_arr.T[::-1]

Let's take the provided sample and check out outputs on an IPython console -

In [48]: image
Out[48]: 
[[1, 1, 5, 9, 9],
 [2, 2, 6, 0, 0],
 [3, 3, 7, 1, 1],
 [4, 4, 8, 2, 2],
 [5, 5, 9, 3, 3]]

In [50]: np.asarray(image).T[::-1].tolist()
Out[50]: 
[[9, 0, 1, 2, 3],
 [9, 0, 1, 2, 3],
 [5, 6, 7, 8, 9],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5]]

Timings on a large 5000 x 5000 sized image

1) Image as a list :

In [53]: image = np.random.randint(0,256,(5000,5000)).tolist()

# @Dima Tisnek's soln
In [54]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.09 s per loop

In [55]: %timeit np.array(image).T[::-1].tolist()
1 loop, best of 3: 1.06 s per loop

Time-complexity

There's no time-complexity involved here (not on computation anyway) and the entire play is about array and list conversion, as shown below when we break down the steps -

In [72]: image_arr = np.array(image)

In [71]: %timeit np.array(image) # convert to array
1 loop, best of 3: 771 ms per loop

In [73]: %timeit image_arr.T[::-1] # perform 90deg rotation
1000000 loops, best of 3: 372 ns per loop

In [74]: %timeit image_arr.T[::-1].tolist() # convert back to list
1 loop, best of 3: 296 ms per loop

2) Image and output as arrays :

In [56]: image = np.random.randint(0,256,(5000,5000))

# @Dima Tisnek's soln
In [57]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.34 s per loop

In [58]: %timeit image.T[::-1]
1000000 loops, best of 3: 363 ns per loop

In [59]: %timeit np.rot90(image)
100000 loops, best of 3: 9.05 µs per loop

The last two NumPy based ones are virtually free as discussed earlier. This is because internally image.T[::-1] is same as input image, but with different stride pattern representation. Let's verify that they are same by checking their memory occupancy -

In [60]: np.shares_memory(image, image.T[::-1])
Out[60]: True

Conversion to list on own-data for slight perf. boost

Closer inspection on list conversion reveals that converting to list when the strided pattern isn't regular (row-order) might not be the most optimal scenario. So, one way would be create a copy of array data once we have the rotated one and then convert. This seems to give around 10% improvement -

In [2]: image = np.random.randint(0,256,(5000,5000)).tolist()

In [8]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.12 s per loop

In [9]: %timeit np.asarray(image).T[::-1].tolist()
1 loop, best of 3: 1.11 s per loop

# Have own-data (copy) and then convert to list
In [10]: %timeit np.asarray(image).T[::-1].copy().tolist()
1 loop, best of 3: 1.01 s per loop

Answer 3

How about using Python built-ins to do the job?

img = [[1, 2, 3], [10, 20, 30], [100, 200, 300]]
list(reversed(list(zip(*img))))
[(3, 30, 300), (2, 20, 200), (1, 10, 100)]

Answer 4

You can rotate the image in place saving on space

def rotate_image(img):
    w = len(img) - 1
    y = 0
    while y < w:
        x = y
        wy = w - y
        while x < wy:
            wx = w - x
            p1 = img[y][x]
            img  [y][x]  = img [wx][y]
            img [wx][y]  = img [wy][wx]
            img [wy][wx] = img  [x][wy]
            img  [x][wy] = p1
            x += 1
        y += 1
    return img

The inner loop is executed ceil(n/2) * floor(n/2) times. However the n is on both sides of the * and only scaled which means its a quadratic and thus the time complexity is O(n²) and storage is O(1)