So the problem of verifying if a list is a subsequence of another came up in a discussion, and I wrote code that seems to work (I haven't rigorously tested it).


def is_subsequence(lst1, lst2):
        *   Finds if a list is a subsequence of another.

        *   Params:
            *   `lst1` (`list`): The candidate subsequence.
            *   `lst2` (`list`): The parent list.
        *   Return:
            *   (`bool`): A boolean variable indicating whether `lst1` is a subsequence of `lst2`.
    l1, l2 = len(lst1), len(lst2)
    if l1 > l2:  #`l1` must be <= `l2` for `lst1` to be a subsequence of `lst2`.
        return False
    i = j = 0
    d1, d2 = l1, l2
    while i < l1 and j < l2:
        while lst1[i] != lst2[j]:
            j += 1
            d2 -= 1
            if d1 > d2:  #At this point, `lst1` cannot a subsequence of `lst2`.
                return False
        i, j, d1, d2 = i+1, j+1, d1-1, d2-1
        if d1 > d2:
            return False
    return True

I'm primarily concerned about performance.

  • \$\begingroup\$ Specify what do you mean by "subsequence". Is [1,1] a subsequence of [1,0,1]? According to your code, it is. If you only want to consider continuous subsequences (eg. [1,1] is not a subsequence of [1,0,1]), you can use a string matching algorithm. The items of the two lists can be viewed as characters of two strings. \$\endgroup\$
    – kyrill
    Mar 14, 2019 at 0:01
  • \$\begingroup\$ [1, 1] is supposed to be a subsequence of [1, 0, 1]. \$\endgroup\$ Mar 15, 2019 at 13:56
  • \$\begingroup\$ In that case, the complexity of your code is optimal. Some optimizations are admissible in specific cases, such as when repeatedly checking the same haystack. Then you might do some preprocessing and save the result, to be able to quickly check whether the needle can possibly be a subsequence or not. For example, make a set of elements of the haystack, and when the needle contains an element which is not in the set, it cannot be a subsequence of the haystack. This would be especially helpful if the haystack is long but contains few unique elements (many repeated elements). \$\endgroup\$
    – kyrill
    Mar 15, 2019 at 16:42
  • \$\begingroup\$ Aah, thanks for the suggestion. \$\endgroup\$ Mar 16, 2019 at 7:26

1 Answer 1



  • Testing

    (I haven't rigorously tested it).

    Well you should write some test to ensure validity of the function. So even after changes you can be sure it will still work. doctest is a pretty nice module to use, and is a nice extension of your docstring

  • Naming

    Variables should have descriptive names!

    lst1, lst2 if it wasn't for that docstring I would not have known what is the subseq and the parent, so instead I propose to rename them to needle and haystack here the intent is more clear

    Same goes for d1, d2... I can see that they are the remaining length of the list, but it is hard to tell from the variable name.

  • for is considered more Pythonic vs while

    For loops are Pythons greatest feature IMHO, they are easy to read and short to write

    You should start writing for loops instead of a while, "Loop like a native" might be an interesting talk to view

  • Too many assignments in a line

    Might be preference, but I find this line hard to read:

    i, j, d1, d2 = i+1, j+1, d1-1, d2-1

    There are too many values with not enough descriptive names on this line


We can instead loop over the haystack and use slicing to compare the sliced haystack with the needle, lastly top it off with the any keyword and write some tests with the doctest module

import doctest

def is_subsequence(needle, haystack):
    Finds if a list is a subsequence of another.

    * args
        needle: the candidate subsequence
        haystack: the parent list

    * returns

    >>> is_subsequence([1, 2, 3, 4], [1, 2, 3, 4, 5, 6])
    >>> is_subsequence([1, 2, 3, 4], [1, 2, 3, 5, 6])
    >>> is_subsequence([6], [1, 2, 3, 5, 6])
    >>> is_subsequence([5, 6], [1, 2, 3, 5, 6])
    >>> is_subsequence([[5, 6], 7], [1, 2, 3, [5, 6], 7])
    >>> is_subsequence([1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, [5, 6], 7])
    return any(
        haystack[i:i+len(needle)] == needle
        for i in range(len(haystack) - len(needle) + 1)

if __name__ == '__main__':
  • 1
    \$\begingroup\$ Thanks for the suggestions. I don't think while is compatible with the algorithm I chose. Also, the algorithm you used is wrong; it tests if the needle is a contiguous subsequence of the haystack, and that's not what I'm trying to do (my use case doesn't require the needle to be contiguous. e.g [1, 1] is a subsequence of [1, 0, 1]). \$\endgroup\$ Mar 15, 2019 at 14:03
  • 3
    \$\begingroup\$ You should have clarified the problem statement in the Question, and if there were any tests, it would have been more obvious ;) \$\endgroup\$
    – Ludisposed
    Mar 15, 2019 at 15:08
  • \$\begingroup\$ Indeed, that's one of the most important functions of tests: conveying to other users what results are expected. \$\endgroup\$ Jul 20, 2022 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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