Given an array of ints, return True if the sequence.. 1, 3, 4 .. appears in the array somewhere.

find_seq_in_array.py

# This method should be pretty clear
# it runs in O(n) time since I am going through the array of ints once
# it ONLY returns true if it succesfully finds the first occurence of my seq in the array of ints


def find_in_seq(array, seq_to_find):
    # Track what has been popped
    popped = []
    len_of_seq = len(seq_to_find)

    # if the array of seq to find is empty return false
    if len_of_seq == 0:
        return False

    for i in xrange(len(array)):
        # check if the end of each array is the same
        if seq_to_find[-1] == array[-1]:
            # add what was popped to the start of the array
            popped.insert(0, seq_to_find.pop())
            # pop the end of the array that we are searching
            array.pop()
        else:
            # if we have pooped something and
            # and the end of the two arrays are not the same
            if len(seq_to_find) != len_of_seq:
                # put back what you have popped
                seq_to_find.extend(popped)
                # reinit the popped array to an empty array
                # and let's start again
                popped = []
            # we will compare the next item at the end of the list
            array.pop()
        # if we have succesfully popped all items in the seq_to_find
        if len(seq_to_find) == 0:
            # item has been found
            return True
    return False


if __name__ == '__main__':
    array1 = [3, 5, 6, 7, 8, 4, 5, 1, 2]
    array2 = [1, 3, 4, 1, 2, 4, 5, 1, 2]
    array3 = [1, 2, 4, 1, 2, 4, 5, 1, 1, 1, 3, 4, 1, 2, 4, 1, 3, 4]
    array4 = [1, 2, 4, 1, 2, 1, 3, 4, 6, 8, 3, 4, 1, 2, 4, 1, 3, 4]

    print "Is seq 1,3,4 in array 2", find_in_seq(array2, [1, 3, 4])
    print "Is seq 1,3,4,6,8 in array 4", find_in_seq(array4, [1, 3, 4, 6, 8])