Python – Closest Pair to Kth index element in Tuple

In the given problem, condition K specifies the maximum allowable difference between corresponding elements of tuples, i.e., it represents the proximity threshold for finding the nearest tuple. The goal is to find the tuple in the list whose elements have the smallest maximum difference compared to the given tuple tup, and this difference should not exceed KKK.

Input : test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)] tup = (17, 23) K = 2 
Output : (19, 23) 

Input : test_list = [(3, 4, 9), (5, 6, 7)] tup = (1, 2, 5) K = 3 
Output : (5, 6, 7)

Method 1: Using enumerate() + loop

The combination of above functions offer brute force way to solve this problem. In this, we use enumerate() to monitor index and abs() to keep the minimum difference updated checked for each element over a loop. 

# Python3 code to demonstrate working of 
# Closest Pair to Kth index element in Tuple
# Using enumerate() + loop

# initializing list
test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]

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

# initializing tuple
tup = (17, 23)

# initializing K 
K = 1

# Closest Pair to Kth index element in Tuple
# Using enumerate() + loop
min_dif, res = 999999999, None
for idx, val in enumerate(test_list):
    dif = abs(tup[K - 1] - val[K - 1])
    if dif < min_dif:
        min_dif, res = dif, idx

# printing result 
print("The nearest tuple to Kth index element is : " + str(test_list[res])) 

The original list is : [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]
The nearest tuple to Kth index element is : (19, 23)

Time complexity: O(n), where n is the length of the test_list.
Auxiliary space: O(1), as we only use a constant number of variables regardless of the input size.

Method 2: Using min() + lambda

The combination of above functions offer shorthand to solve this problem. In this, we use min() to find minimum element difference and lambda function is used to perform iterations and computations. 

# Python3 code to demonstrate working of 
# Closest Pair to Kth index element in Tuple
# Using min() + lambda

# initializing list
test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]

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

# initializing tuple
tup = (17, 23)

# initializing K 
K = 1

# Closest Pair to Kth index element in Tuple
# Using min() + lambda
res = min(range(len(test_list)), key = lambda sub: abs(test_list[sub][K - 1] - tup[K - 1]))

# printing result 
print("The nearest tuple to Kth index element is : " + str(test_list[res])) 

The original list is : [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]
The nearest tuple to Kth index element is : (19, 23)

Time complexity: O(n), where n is the length of the input list
Auxiliary space: O(1), since we are not using any additional data structures or variables proportional to the size of the input list.

Method 3:Using a lambda function and the min() function

Step-by-step algorithm:

1. Initialize the list of tuples, the target tuple and the index K.
2. Use the min() function and a lambda function to find the tuple in the list with the smallest absolute difference between its Kth element and the Kth element of the target tuple.
3. Assign the result of the min() function to a variable named “res”.
4. Print the value of “res” as the nearest tuple to the Kth index element of the target tuple.

# initializing list
test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]

# initializing tuple
tup = (17, 23)

# initializing K
K = 1

# Using a lambda function and the min() function
res = min(test_list, key=lambda x: abs(x[K-1] - tup[K-1]))

# printing result
print("The nearest tuple to Kth index element is : " + str(res))

The nearest tuple to Kth index element is : (19, 23)

Time complexity: O(n), where n is the length of the list of tuples. This is because the min() function iterates over the list once to find the tuple with the smallest absolute difference between its Kth element and the Kth element of the target tuple.

Auxiliary space: O(1), since we only store a constant amount of data, such as the list of tuples, the target tuple, the index K, and the result tuple.

Method 4:Using the heapq.nsmallest() function: 

Algorithm:

1.Initialize a list of tuples.
2.Initialize the tuple we want to find the closest match for.
3.Initialize the index of the tuple we want to compare.
4.Use the heapq.nsmallest() function to find the smallest element in the list based on the difference between the tuple elements at the specified index.
5.Return the closest tuple.

import heapq

# initializing the list of tuples
test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]

# initializing the target tuple
tup = (17, 23)

# initializing the index of the element to compare in each tuple
K = 1

# using the heapq.nsmallest() function to get the tuple with the smallest difference between the Kth element and the corresponding element in the target tuple
res = heapq.nsmallest(1, test_list, key=lambda x: abs(x[K-1] - tup[K-1]))[0]

# printing the result
print("The nearest tuple to Kth index element is : " + str(res))
#This code is contributed by Jyothi pinjala.

The nearest tuple to Kth index element is : (19, 23)

Time complexity:
The time complexity of this code is O(nlogk), where n is the number of elements in the list and k is the value passed as the first argument to heapq.nsmallest(). In this case, k is 1, so the time complexity is effectively O(log n).

Space complexity:
The space complexity of this code is O(k), where k is the value passed as the first argument to heapq.nsmallest(). In this case, k is 1, so the space complexity is effectively constant.

 Method 5 : using the sorted() function with a custom key. 

step-by-step approach :

Step 1: Initialize the list of tuples, the target tuple, and the index of the element to compare in each tuple.

Step 2: Define a custom key function that takes a tuple as input and returns the absolute difference between the Kth element of the tuple and the corresponding element in the target tuple.

Step 3: Use the sorted() function to sort the list of tuples based on the custom key function.

Step 4: Retrieve the first tuple from the sorted list.

Step 5: Print the result.

# initializing the list of tuples
test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]

# initializing the target tuple
tup = (17, 23)

# initializing the index of the element to compare in each tuple
K = 1

# define a custom key function
def key_func(t):
    return abs(t[K-1] - tup[K-1])

# use the sorted() function to sort the list of tuples based on the custom key function
sorted_list = sorted(test_list, key=key_func)

# retrieve the first tuple from the sorted list
res = sorted_list[0]

# print the result
print("The nearest tuple to Kth index element is : " + str(res))

The nearest tuple to Kth index element is : (19, 23)

Time complexity: O(n log n), where n is the length of the list of tuples. The sorted() function uses the Timsort algorithm, which has a time complexity of O(n log n).

Auxiliary space: O(n), where n is the length of the list of tuples. The sorted() function creates a new sorted list, which has the same length as the original list.

Method 6: Using a List Comprehension and min

This code snippet calculates the tuple from test_list that is closest to the target_tuple based on the Euclidean distance. It creates a list of tuples containing each original tuple and its distance to the target, finds the one with the minimum distance using a key in the min function, and prints that tuple as the output.

test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]
target_tuple = (17, 23)
k = 2

result = min([(pair, ((pair[0] - target_tuple[0])**2 + (pair[1] - target_tuple[1])**2)**0.5) for pair in test_list], key=lambda x: x[1])[0]
print("Output:", result)

('Output:', (19, 23))

Time complexity:O(n)

Auxiliary space:O(n)

manjeet_04

Follow

Improve