Sometimes we encounter the problem of checking if one list is just an extension of the list i.e just a superset of one list. These kinds of problems are quite popular in competitive programming. Having shorthands for it helps the cause. Let’s discuss various ways to achieve this particular task.
Method #1: Using all() function
all() is used to check all the elements of a container in just one line. Checks for all the elements of one list for existence in other lists.
Python3
# Python3 code to demonstrate# to check if list is subset of other# using all()# initializing listtest_list = [9, 4, 5, 8, 10]sub_list = [10, 5, 4]# printing original listsprint("Original list : " + str(test_list))print("Original sub list : " + str(sub_list))# using all() to# check subset of listflag = 0if(all(x in test_list for x in sub_list)): flag = 1# printing resultif (flag): print("Yes, list is subset of other.")else: print("No, list is not subset of other.") |
Output :
Original list : [9, 4, 5, 8, 10] Original sub list : [10, 5, 4] Yes, list is subset of other.
Time complexity: O(n) where n is the length of the sub_list.
Auxiliary space: O(1), as the program only requires variables to store the lists and a flag variable.
Method #2 : Using set.issubset() function
The most used and recommended method to check for a sublist. This function is tailor made to perform the particular task of checking if one list is a subset of another.
Python3
# Python3 code to demonstrate# to check if list is subset of other# using issubset()# initializing listtest_list = [9, 4, 5, 8, 10]sub_list = [10, 5]# printing original listsprint("Original list : " + str(test_list))print("Original sub list : " + str(sub_list))# using issubset() to# check subset of listflag = 0if(set(sub_list).issubset(set(test_list))): flag = 1# printing resultif (flag): print("Yes, list is subset of other.")else: print("No, list is not subset of other.") |
Output :
Original list : [9, 4, 5, 8, 10] Original sub list : [10, 5] Yes, list is subset of other.
Time complexity: O(m+n), where m and n are the lengths of the input lists.
Auxiliary space: O(m+n), because we create sets from the input lists, which can take up to O(m+n) space in the worst case.
Method #3 : Using set.intersection() function
Yet another method dealing with sets, this method checks if the intersection of both the lists ends up to be the sub list we are checking. This confirms that one list is a subset of the other.
Python3
# Python3 code to demonstrate# to check if list is subset of other# using intersection()# initializing listtest_list = [9, 4, 5, 8, 10]sub_list = [10, 5]# printing original listsprint("Original list : " + str(test_list))print("Original sub list : " + str(sub_list))# using intersection() to# check subset of listflag = 0if((set(sub_list) & set(test_list)) == set(sub_list)): flag = 1# printing resultif (flag): print("Yes, list is subset of other.")else: print("No, list is not subset of other.") |
Output :
Original list : [9, 4, 5, 8, 10] Original sub list : [10, 5] Yes, list is subset of other.
Time complexity: The code first converts both lists into sets, which takes O(n) time where n is the size of the list.
Auxiliary space: The code creates two sets, one for test_list and one for sub_list, which takes O(n) and O(m) space respectively.
Method #4 : Using iteration and counter
Using the count of elements in both lists to check whether the second list is a subset of the first list.
Python3
# Python3 code to demonstrate# to check if list is subset of other# Importingfrom collections import Counterdef checkInFirst(a, b): # getting count count_a = Counter(a) count_b = Counter(b) # checking if element exists in second list for key in count_b: if key not in count_a: return False if count_b[key] > count_b[key]: return False return True# initializing lista = [1, 2, 4, 5]b = [1, 2, 3]# Calling functionres = checkInFirst(a, b)# Printing listprint("Original list : " + str(a))print("Original sub list : " + str(b))if res == True: print("Yes, list is subset of other.")else: print("No, list is not subset of other.")# Added by Paras Jain(everythingispossible) |
Output :
Original list : [1, 2, 4, 5] Original sub list : [1, 2, 3] No, list is not subset of other.
Method #5 : Using set index
Python3
# Python3 code to demonstrate# to check if list is subset of other# initializing listone = [1, 2, 3, 4, 5]two = [1, 2]# using set to find if element exists in another listresult = set(x in one for x in two)flag = 0for ans in result: if ans == False: flag = 1# Printing listprint("Original list : " + str(one))print("Original sub list : " + str(two))if flag == 0: print("Yes, list is subset of other.")else: print("No, list is not subset of other.")# Added by Paras Jain(everythingispossible) |
Output :
Original list : [1, 2, 3, 4, 5] Original sub list : [1, 2] Yes, list is subset of other.
Time Complexity: O(n), where n is length of result list.
Auxiliary Space: O(n), where n is length of result list.
Method #6: Using functools.reduce
Python3
from functools import reducefrom operator import and_ # main containing checkerdef contains(superset, subset) -> bool: # creates a list of boolean values and # combines them using the and operator return reduce(and_, [i in superset for i in subset])# creating some lists for testingsuperset = [3, 4, 5, 6]subset = [4, 5]not_subset = [4, 5, 7]# print whether or not the# subset is in the supersetprint(f"{subset} is in {superset}: {contains(superset,subset)}")print(f"{not_subset} is in {superset}: {contains(superset,not_subset)}") |
Output:
[4, 5] is in [3, 4, 5, 6]: True [4, 5, 7] is in [3, 4, 5, 6]: False
Method#7: Using Recursive method.
Algorithm:
- Define a function checkInFirstRecursive that takes in two lists a and b.
- Check if the list b is empty. If so, return True and terminate the function.
- Check if the count of the first element of list b in list a is less than the count of the same element in list b. If so, return False and terminate the function.
- Recursively call the checkInFirstRecursive function with the sublist of a starting from the index of the first element of b, and the sublist of b starting from the second element.
- Initialize two lists a and b.
- Call the checkInFirstRecursive function with the lists a and b.
- If the returned value is True, print a message indicating that b is a subset of a. Otherwise, print a message indicating that it is not a subset.
Python3
def checkInFirstRecursive(a, b): if not b: return True if a.count(b[0]) < b.count(b[0]): return False return checkInFirstRecursive(a[a.index(b[0]):], b[1:])# initializing lista = [1, 2, 4, 5]b = [1, 2, 3]# Calling functionres = checkInFirstRecursive(a, b)# Printing listprint("Original list : " + str(a))print("Original sub list : " + str(b))if res == True: print("Yes, list is subset of other.")else: print("No, list is not subset of other.")#this code contributed by tvsk |
Original list : [1, 2, 4, 5] Original sub list : [1, 2, 3] No, list is not subset of other.
Time Complexity:
The worst-case time complexity of the algorithm is O(n * m), where n and m are the lengths of the lists a and b, respectively. This is because the algorithm iterates over all the elements in both lists, and the index method is called on list a for every element in list b.
Auxiliary Space:
The space complexity of the algorithm is proportional to the maximum depth of the recursive call stack, which is equal to the length of list b. Therefore, the space complexity of the algorithm is O(m), where m is the length of the list b.
