Python – Extract list with difference in extreme values greater than K

0 0 3 minutes read

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 list
test_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K 
K = 5
 
# max() and min() getting extreme difference
res = [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 list
test_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K 
K = 5
 
# max() and min() getting extreme difference
res = 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 list
test_list = [[3, 5, 1], [9, 1, 2], [3, 4, 2], [1, 10, 2]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K
K = 5
 
# initializing empty list to store qualifying sublists
res = []
 
# iterating over the list of lists
for 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))

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(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.