Python | Check if a list is contained in another list - GeeksforGeeks (2024)

Given two lists A and B, write a Python program to Check if list A is contained in list B without breaking A’s order.

Examples:

Input : A = [1, 2], B = [1, 2, 3, 1, 1, 2, 2]Output : True

Input : A = ['x', 'y', 'z'], B = ['x', 'a', 'y', 'x', 'b', 'z']Output : False

Approach #1: Naive Approach

A simple naive approach is to use two for loops and check if the whole list A is contained within list B or not. If such a position is met in list A, then break the loop and return true, otherwise false.

True

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Approach #2: Using list comprehension

A more efficient approach is to use List comprehension. We first initialize ‘n’ with the length of A. Now use a for loop till len(B)-n and check in each iteration if A == B[i:i+n] or not.

True

Time complexity: O(n^2). where A and B are both of length n,
Auxiliary space: O(n), where n is the length of B.

Approach #3: Using join and map module

Here we use join to join both lists to strings and then use in operator to check if list A is contained in B or not.

False

Time complexity: O(m*n) , where m is the length of A and n is the length of B.
Auxiliary space: O(1),where m is length of A and n is the length of B.

Approach #4: Using regular expressions

To check if a list is contained in another list using the Python re (regular expression) module, you can use the re.findall() function to find all instances of list A within list B as a string. If the number of instances found is greater than 0, it means that list A is contained within list B.

Here is an example of how this can be done:

False

Time complexity: O(m*n) , where m is length of A and n is length of B.
Auxiliary space: O(1), where m is length of A and n is length of B.

Approach #5: Using Recursive method

Steps:

1. If list A is empty, return True, as an empty list is always a sublist of any list.
2. If list B is empty, return False, as an empty list cannot contain any sublist.
3. If A[0] matches B[0], recursively check the rest of the elements of A and B by calling the is_sublist method with A[1:] and B[1:].
4. If A[0] does not match B[0], recursively check if A is a sublist of the remaining elements of B by calling the is_sublist method with A and B[1:]
5. Return True if the previous recursive call returned True, indicating that A is a sublist of B, or False otherwise.

True

Time complexity: O(n * m), where n is the length of list A and m is the length of list B. This is because the function needs to traverse both lists in the worst-case scenario, and the length of list B may need to be traversed multiple times depending on the position of the matching element of A.

Auxiliary space: O(max(n, m)), where n is the length of list A and m is the length of list B. This is because the function makes recursive calls, and each call adds a new stack frame to the call stack, potentially using up additional memory. However, the maximum depth of the call stack is bounded by the maximum length of A or B, so the space used is proportional to the maximum of the two lengths.

Approach #6: Using Numpy

Note: install numpy module using command “pip install numpy”

Steps:

1. Import numpy module and define a function named “check_list_contained” that takes two parameters, “A” and “B”.
2. Convert “A” and “B” to numpy arrays “A_arr” and “B_arr” respectively.
3. Loop through “B_arr” using a for loop and range function for index “i” in range of length of “B_arr”.
4. Check if the subarray of “B_arr” starting from index “i” and of length equal to the length of “A_arr” is equal to “A_arr” using the numpy array_equal() function.
5. If the above condition is true, then return True, as the list “A” is contained in the list “B”.
6. If the loop finishes execution without returning True, return False, as the list “A” is not contained in the list “B”.
7. Test the function by passing two list parameters “A” and “B”.
8. Print the result of the function call.

Output:

TrueFalse

Time complexity: O(n^2), where n is the length of B.
Auxiliary space: O(n), where n is the length of B.