Given a Matrix, filter all the rows which contain all elements in the given number range.
Input : test_list = [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]], i, j = 2, 5
Output : [[3, 2, 4, 5, 10], [2, 3, 4, 5, 6, 7]]
Explanation : 2, 3, 4, 5 all are present in above rows.Input : test_list = [[3, 2, 4, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]], i, j = 2, 5
Output : [[2, 3, 4, 5, 6, 7]]
Explanation : 2, 3, 4, 5 all are present in above rows.
Method #1 : Using all() + list comprehension
In this, we check for all the elements in range for presence using all() and list comprehension is used for the task of iteration of elements.
Python3
# Python3 code to demonstrate working of# Filter Rows with Range Elements# Using all() + list comprehension# initializing listtest_list = [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]]# printing original listprint("The original list is : " + str(test_list))# initializing rangei, j = 2, 5# checking for presence of all elements using in operatorres = [sub for sub in test_list if all(ele in sub for ele in range(i, j + 1))]# printing resultprint("Extracted rows : " + str(res)) |
The original list is : [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]] Extracted rows : [[3, 2, 4, 5, 10], [2, 3, 4, 5, 6, 7]]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using filter() + lambda + all()
In this, task of filtering is done using filter() and lambda function, all() is again used to ensure all elements presence in range.
Python3
# Python3 code to demonstrate working of# Filter Rows with Range Elements# Using filter() + lambda + all()# initializing listtest_list = [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]]# printing original listprint("The original list is : " + str(test_list))# initializing rangei, j = 2, 5# filter() and lambda used to filter elementsres = list(filter(lambda sub: all( ele in sub for ele in range(i, j + 1)), test_list))# printing resultprint("Extracted rows : " + str(res)) |
The original list is : [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]] Extracted rows : [[3, 2, 4, 5, 10], [2, 3, 4, 5, 6, 7]]
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”. filter() + lambda + all() performs n*n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #3:Using itertools.filterfalse() method
Python3
# Python3 code to demonstrate working of# Filter Rows with Range Elementsimport itertools# initializing listtest_list = [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]]# printing original listprint("The original list is : " + str(test_list))# initializing rangei, j = 2, 5res = list(itertools.filterfalse(lambda sub: not all( ele in sub for ele in range(i, j + 1)), test_list))# printing resultprint("Extracted rows : " + str(res)) |
The original list is : [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]] Extracted rows : [[3, 2, 4, 5, 10], [2, 3, 4, 5, 6, 7]]
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Method #4:Using List Comprehension and Set Intersection:
Algorithm:
- Initialize the input list and range values.
- Use list comprehension to iterate through each sublist in the input list.
- Check if the set intersection of the sublist and the range values is equal to the range values set.
- If it is, append the sublist to the result list.
- Print the result list.
Python3
# initializing listtest_list = [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]]# printing original listprint("The original list is : " + str(test_list))i, j = 2, 5res = [lst for lst in test_list if set(range(i, j+1)).intersection(lst) == set(range(i, j+1))]print("Extracted rows: ", res)#This code is contributed by Jyothi pinjala |
The original list is : [[3, 2, 4, 5, 10], [3, 2, 5, 19], [2, 5, 10], [2, 3, 4, 5, 6, 7]] Extracted rows: [[3, 2, 4, 5, 10], [2, 3, 4, 5, 6, 7]]
Time complexity:
The time complexity of this code is O(nm), where n is the number of sublists in the input list and m is the average length of each sublist. This is because we are iterating through each sublist and performing set operations on them.
Space complexity:
The space complexity of this code is O(k), where k is the length of the range between i and j. This is because we are using a set to store the range values.
