Python - Remove Tuples with difference greater than K

Given Dual Tuples List, remove pairs with differences greater than K.

Input : test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)], K = 6 
Output : [(4, 8), (9, 12), (1, 7)] 
Explanation : 4 (8 - 4), 3 (12 - 9) and 6 are all not greater than 6, hence retained.

Input : test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)], K = 3 
Output : [(9, 12)] 
Explanation : 3 (12 - 9) is not greater than 3, hence retained. 

Method #1 : Using list comprehension

In this, we perform filtering by testing the absolute difference using abs(), if found smaller than K, its retained, hence greater than K difference tuples are removed.

# Python3 code to demonstrate working of
# Remove Tuples with difference greater than K
# Using list comprehension

# initializing list
test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]

# printing original list
print("The original list is : " + str(test_list))

# initializing K
K = 5

# filtering using list comprehension, checking for smaller than K diff.
res = [sub for sub in test_list if abs(sub[0] - sub[1]) <= K]

# printing result
print("Tuples List after removal : " + str(res))

The original list is : [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]
Tuples List after removal : [(4, 8), (9, 12)]

Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(m), where m is the length of the output list. 

Method #2 : Using filter() + lambda + abs()

In this, task of filtering is performed using filter() and lambda function, abs() is used to get the absolute difference.

# Python3 code to demonstrate working of
# Remove Tuples with difference greater than K
# Using filter() + lambda + abs()

# initializing list
test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]

# printing original list
print("The original list is : " + str(test_list))

# initializing K
K = 5

# Using filter() and lambda function for filtering
res = list(filter(lambda sub: abs(sub[0] - sub[1]) <= K, test_list))

# printing result
print("Tuples List after removal : " + str(res))

The original list is : [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]
Tuples List after removal : [(4, 8), (9, 12)]

Time complexity: O(n), where n is the length of the input list test_list.
Auxiliary space: O(1), as we are not using any additional data structures to store the intermediate results.

Method #3: Using a for loop to iterate through the list and append tuples that meet the criteria to a new list.

test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]

K = 5

res = []
# Iterate through the tuples in the list
for tup in test_list:
    # Check if the absolute difference between the elements
    # of the tuple is less than or equal to K
    if abs(tup[0] - tup[1]) <= K:
        # If the difference is smaller than K, append the tuple
        # to the result list
        res.append(tup)

# Print the list of tuples after removing the ones with larger difference
print("Tuples List after removal : " + str(res))

Tuples List after removal : [(4, 8), (9, 12)]

Time Complexity: O(n), where n is the number of tuples in the input list. This is because we are iterating through each tuple in the list once, and performing a constant number of operations (i.e., the absolute value calculation and comparison) for each tuple.
Auxiliary Space: O(n), This method uses additional space to store the result list res, which has a maximum size of n (i.e., when all tuples meet the criteria).

Method #4: Using a generator expression

Step-by-step approach:

• Initialize the list test_list.
• Initialize the value of K.
• Use a generator expression to iterate through the tuples in test_list and yield the tuples that meet the criteria (absolute difference between elements is less than or equal to K).
• Convert the generator expression to a list and assign it to the variable res.
• Print the resulting list res.

Below is the implementation of the above approach:

# Python3 code to demonstrate working of
# Remove Tuples with difference greater than K
# Using generator expression

# initializing list
test_list = [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]

# printing original list
print("The original list is : " + str(test_list))

# initializing K
K = 5

# using generator expression to yield tuples that meet the criteria
res = (sub for sub in test_list if abs(sub[0] - sub[1]) <= K)

# converting generator expression to list
res = list(res)

# printing result
print("Tuples List after removal : " + str(res))

The original list is : [(4, 8), (1, 7), (9, 12), (3, 12), (2, 10)]
Tuples List after removal : [(4, 8), (9, 12)]

Time complexity: O(n)
Auxiliary space: O(n) for the resulting list res