# Compare two lists to see if one is a rotation of the other 2

Second attempt to solve this rotation problem, implemented a double ended queue as was suggested in a comment of my first attempt. So did I finally do the problem some justice or is there perhaps a better solution? Also anything I can and should clean up? I wanted to thank everyone from my previous post for their help and suggestions!

'''
Attempt 2
Problem statement: Given 2 integer arrays, determine if the 2nd array is a rotated version of the 1st array.
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3}

@author: Anonymous3.1415
'''

from collections import deque

def is_rotated(lst1, lst2):
'''is lst2 a rotation of lst1 '''

if len(lst1) != len(lst2):
return False
if lst1 == [] and lst2 == []:
return True

d_lst1 = deque(lst1)
d_lst2 = deque(lst2)

#rotate all possible rotations to find match
for n in range(len(d_lst1)):
d_lst2.rotate(n)
if d_lst2 == d_lst1:
return True
d_lst2.rotate(-n)
return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

If you compare one of the lists with all the rotations of the other list, this will take $\Theta(n^2)$ in the worst case.

For example, if we make test cases like this:

from timeit import timeit
def test(n):
l1 = [0] * n
l2 = [0] * (n - 1) + [1]
return timeit(lambda:is_rotated(l1, l2), number=1)

then the quadratic runtime can be clearly seen in the timings:

>>> test(10**3)
0.009426131844520569
>>> test(10**4)
0.5701698779594153
>>> test(10**5)
57.70295810396783

There are a couple of ways to solve this problem in linear time:

1. Search for one list in the concatenation of the other list with itself, using a search algorithm that has linear time in the worst case, for example Knuth–Morris–Pratt.

Here's an illustration of this approach using strings instead of lists: