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(n2), 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]
  • 4
    O(N^2) wrt. N being the number of pixels or side of the squre? – Dima Tisnek Sep 20 at 5:48
  • 1
    In your analysis, what exactly is "n"? Are you implying that the matrix is necessarily square? – 200_success Sep 20 at 5:49
  • @200_success Yes the matrix is expected to always be proportional, i.e., the same length everywhere. – NewbieWanKenobi Sep 20 at 5:58
  • 3
    Is it acceptable to rotate the matrix in place, without creating a new one? Is it acceptable to create a new class which redefines .__getitem__ for a rotation in O(1)? – Eric Duminil Sep 20 at 8:03
  • 1
    @NewbieWanKenobi: Yes, you can re-assign 4 values at the same time. As an example with a 2x2 matrix : m = [[1, 2], [3, 4]]; m[1][0], m[0][0], m[1][1], m[0][1] = m[0][0], m[0][1], m[1][0], m[1][1]; m – Eric Duminil Sep 20 at 19:30
up vote 21 down vote accepted

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

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

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)]
  • Very nice but I'd like the output to be formatted like the input, or an array matrix. – NewbieWanKenobi Sep 20 at 6:22
  • 4
    @NewbieWanKenobi You can map the list constructor to zip(*img) if you don't like tuples in your output. Alternatively, [list(row) for row in zip(*img)][::-1] does the same but feels more readable (to me). – Mathias Ettinger Sep 20 at 7:40

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.