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

Question

Going through a list of common interview question, this was the next one. Any suggestions on performance and improvement? What would be a better implementation of this? Also correct me if I'm wrong, this would be \$O(n)\$ complexity?

'''
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
'''

#@cmp_arr, is the array being compared to see if it is a rotation
def is_rotated(int_arr, cmp_arr):

    #lengths of arrays are the same and not equal to zero?
    if len(int_arr) != len(cmp_arr) or len(int_arr) == 0:
        return False

    #does array contain same numbers?
    if not set(int_arr) <= set(cmp_arr) and not set(int_arr) >= set(cmp_arr):
        return False

    #Find start of first list in the second
    index = 0
    while int_arr[0] != cmp_arr[index]:
        index += 1

    #split list at index point, compare the lists
    cmp_arr = cmp_arr[index:] + cmp_arr[:index]
    index = 0
    for x in int_arr:
        if x != cmp_arr[index]:
            return False
        index += 1

    return True

int_arr = [1,2,3,4,6,4,7]
cmp_arr = [6,4,7,1,2,3,4]
print(is_rotated(int_arr, cmp_arr))

Answer 1

Naming

Your 2 arrays are used the same way, it is a bit weird to have 2 different names for them. Maybe int_arr1 and int_arr2 would be better names. Also the fact that they contain integers may be irrelevant for the naming: arr1 and arr2 would do the trick (or lst1 and lst2 because the corresponding Python primitive data structure is list).

Problem with the check for length equal to 0

Checking for identical lengths as the beginning of the function is a nice touch.

However, the or len(lst1) == 0 condition makes me uneasy. It only makes a different when the first part of the check was false and the second part is true which means: len(lst1) == len(lst2) == 0 which really means: lst1 == lst2 == [].

I'd expect the empty array to be a rotation of the empty array. The alternative would be to document the function to precise that only non-trivial rotations are considered (which is not the case at the moment). The easy fix is probably to remove this test or to return True in that case (or whenver lst1 == lst2).

Comments

Commenting your code is nice but adding obvious comments doesn't help anyone. There is a fine line between too many comments and not enough comments.

I'd get rid of #lengths of arrays are the same and not equal to zero? for instance.

On the other hand, #@cmp_arr, is the array being compared to see if it is a rotation could be kept somehow. This should be moved in the function docstring. Also, Python has a Docstring convention called PEP 257. You could write:

def is_rotated(lst1, lst2):
    """Test whether list lst1 is a rotation of list lst2."""

Same value computed multiple times

You compute set(lst1) multiple times which is not as efficient as it could be (which is sad for something meant to be an optimisation).

#does array contain same numbers?
s1 = set(lst1)
s2 = set(lst2)
if not s1 <= s2 and not s1 >= s2:
    return False

Optimisation does not work

I guess the point of the optimisation would be to detect situations like:

lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
print(is_rotated(lst1, lst2))

lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
print(is_rotated(lst1, lst2))

Unfortunately, this is not detected.

I guess instead of not s1 <= s2 and not s1 >= s2, you meant: not s1 <= s2 or not s1 >= s2 which is equivalent to not (s1 <= s2 and s1 >= s2) which is equivalent to the more straight-forward: s1 != s2.

In any case, as pointed out by Oscar Smith, this optimisation may not be worth doing.

Reusing existing functions

Looking for index can be done with the already existing function: index = lst2.index(lst1[0]).

Loop like a native

Your final loop is not really Pythonic. Most of the time in Python, you can avoid messing with indices. I hightly recommand Ned Batchelder's talk: "Loop like a native".

In your case, we can improve your code in multiple steps. (Some of the steps are pretty artificial in your case but I use them to show you the different functions you have in your Python toolbox).

Introducing enumerate to get rid of the code to track index:

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for i, x in enumerate(lst1):
    if x != rot2[i]:
        return False
return True

Using zip to avoid accessing rot2 by index:

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for x1, x2 in zip(lst1, rot2):
    if x1 != x2:
        return False
return True

Using all to make things more concise:

return all(x1 == x2 for x1, x2 in zip(lst1, rot2))

The final revelation: all this is not needed:

return lst1 == rot2

At this point, the code looks like:

def is_rotated(lst1, lst2):
    """Test whether list lst1 is a rotation of list lst2."""
    if len(lst1) != len(lst2):
        return False

    if lst1 == lst2:
        return True

    if set(lst1) != set(lst2):
        return False

    index = lst2.index(lst1[0])

    #split list at index point, compare the lists
    rot2 = lst2[index:] + lst2[:index]
    return lst1 == rot2

Broken code

As pointed out by Oscar Smith, your code does not work.

For that kind of programming task, it is very easy to write tests to help you catch issues. These can be written before, during and after writing the code. You could use a proper testing framework or just simple assertions like:

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

Answer 2

While this is O(n), it isn't nearly as fast as it could be.

Your first check is a good one because it is O(1), and will be hit for random lists a fair amount. The second however is not. by finding the unique elements, you end up doing a screen that costs an amount of time comparable to solving the actual problem.

The next piece of your code is actually broken, as it only finds the first match instead of all possible matches. In fact, when you fix this bug, your code will be O(n^2) in the worst case (if one is [0]*1000+[1,0] and the other is [0]*1000+[0,1])