Given a list of lists. The task is to filter all rows whose difference in min and max values is greater than K.
Examples:
Input : test_list = [[13, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]], K = 5
Output : [[9, 1, 2], [1, 10, 2], [13, 5, 1]]
Explanation : 8, 9, 12 are differences, greater than K.Input : test_list = [[13, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]], K = 15
Output : []
Explanation : No list with diff > K.
Method #1 : Using list comprehension + min() + max()
In this, we perform task of iteration using list comprehension and the task of checking is done using the comparison operator. Values are computed using max() and min().
Python3
# Python3 code to demonstrate working of # Filter rows with Extreme values greater than K# Using min() + max() + list comprehension# initializing listtest_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 5# max() and min() getting extreme differenceres = [sub for sub in test_list if max(sub) - min(sub) > K]# printing result print("Filtered rows : " + str(res)) |
Output:
The original list is : [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]] Filtered rows : [[9, 1, 2], [1, 10, 2]]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using filter() + lambda + min() + max()
In this, we perform task of filtering using filter() and lambda, rest min() and max(), are used to get extreme values difference.
Python3
# Python3 code to demonstrate working of # Filter rows with Extreme values greater than K# Using filter() + lambda + min() + max()# initializing listtest_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 5# max() and min() getting extreme differenceres = list(filter(lambda sub : max(sub) - min(sub) > K, test_list))# printing result print("Filtered rows : " + str(res)) |
Output:
The original list is : [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]] Filtered rows : [[9, 1, 2], [1, 10, 2]]
Time Complexity: O(n) where n is the number of elements in the list “test_list”. This is because we’re using the built-in filter() + lambda + min() + max() which all has a time complexity of O(n) in the worst case.
Auxiliary Space: O(1), no extra space is required
Method #3: Using a for loop to iterate over the list of lists and append qualifying sublists to a new list
- Initialize the list of lists.
- Initialize the value of K.
- Initialize an empty list to store qualifying sublists.
- Iterate over the list of lists using a for loop.
- Check if the difference between the maximum and minimum values of the current sublist is greater than K.
- If the difference is greater than K, append the current sublist to the result list.
- Print the filtered rows.
Python3
# Python3 code to demonstrate working of # Filter rows with Extreme values greater than K# Using for loop# initializing listtest_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 5# initializing empty list to store qualifying sublistsres = []# iterating over the list of listsfor sublist in test_list: # checking if the difference between the maximum and minimum values of the sublist is greater than K if max(sublist) - min(sublist) > K: # appending the sublist to the result list res.append(sublist)# printing result print("Filtered rows : " + str(res)) |
The original list is : [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]] Filtered rows : [[9, 1, 2], [1, 10, 2]]
Time complexity: O(nm), where n is the number of sublists and m is the length of the longest sublist. The for loop iterates over each sublist once
.Auxiliary space: O(k), where k is the number of qualifying sublists. The result list stores the qualifying sublists.
