Finding the closest pair of numbers which add to a target number

Question

This function takes two lists of same length and a target number: the number which is to be summed. The function then returns a list of pairs whose sum is closest to the target number than any other pairs. It also finds the pair whose sum is equal to the target number.

def pair_finder(list1, list2, t):
 list1.sort()
 list2.sort()
 list1.reverse()
 t_low = list1[-1] + list2[0]
 t_high = list1[0] + list2[-1]
 pairs_low = []
 pairs_high = []
 pairs_equal = []
 for i in list1:
 k = 0
 for j in list2:
 if i + j < t:
 if i + j > t_low:
 pairs_low.clear()
 t_low = i + j
 pairs_low.append([i, j])
 elif (i + j == t_low):
 pairs_low.append([i, j])
 if i + j > t:
 if i + j < t_high:
 pairs_high.clear()
 t_high = i + j
 pairs_high.append([i, j])
 list2 = list2[k:]
 break
 elif i + j == t_high:
 pairs_high.append([i, j])
 if i + j == t:
 pairs_equal.append([i, j])
 k += 1
 pairs = []
 for q in pairs_low:
 pairs.append(q)
 for w in pairs_high:
 pairs.append(w)
 for r in pairs_equal:
 pairs.append(r)
 return pairs
while True:
 try:
 l1 = []
 l2 = []
 li = input("enter the first sequence of numbers by giving exactly one space between numbers:")
 for i in li.split(" "):
 l1.append(int(i))
 lj = input("enter the second sequence of numbers by giving exactly one space between numbers:")
 for j in lj.split(" "):
 l2.append(int(j))
 if len(l1) == len(l2):
 target = int(input("enter the target number: "))
 break
 else:
 print("the length of both sequences should be same!")
 l1 = []
 l2 = []
 except ValueError:
 print("only integer type values are allowed!")
for pair in pair_finder(l1, l2, target):
 print(pair)

Example:
Let list 1 be 2 98 63 41 25 27 -51 48 18 54 31 28 55 11
and list 2 be 21 56 87 65 21 12 75 41 33 91 32 15 8 -35
and target number be 43 hence the
pairs (15, 27),(33, 11),(41, 2),(32, 11),(15, 28),(12, 31)

• πάντα ῥεῖ: Your code is broken (regarding the correct indentation), also you missed to provide a description what it is purposed to do. Your question is off-topic here, fix these things first before asking for a review please.
• Peilonrayz: @πάνταῥεῖ The code is a C&P error, and can be fixed by anyone - including you. The title includes the description, what more explanation do you need to understand this?
• Peilonrayz: Yeah you've broke the code again, after I fixed it...
• πάντα ῥεῖ: @Peilonrayz Isn't it the duty of the author to post working code here?
• Peilonrayz: @πάνταῥεῖ The reason the code is not working is because SE has a non-standard method of displaying code blocks. Causing 'code problems' for people that are new to the system. Please perform a quick browse of meta and you'll see more information.

Answer 1

Human Computer Interaction

Prompts

 li = input("enter the first sequence of numbers by giving exactly one space between numbers:")
 lj = input("enter the second sequence of numbers by giving exactly one space between numbers:")

These are awfully long prompts for the user to enter in a list of values after. Maybe instructions, and then two short input prompts?

 print("Enter two space separated integer number sequences, of the same length.")
 li = input("First sequence: ")
 lj = input("Second sequence: ")

White-space separators

li.split(" ") will separate a string into a number of items separated by exactly one space. If the user wants to enter a single digit number on one line, and a two digit number on the next, and keep the columns of numbers lined up, they can't use extra spaces.

.split(), with no arguments, will split a string into a number of items separated by one or more white-space characters.

>>> " 2 3 \t \n 4 \r 5 ".split()
['2', '3', '4', '5']

No hard requirements to use exactly one space. And leading and trailing spaces are trimmed, too!

Unexpected Behaviour

def pair_finder(list1, list2, t):
 list1.sort()
 list2.sort()
 ...

After calling pair_finder(l1, l2, target), you'll find that l1 and l2 have been sorted! The caller probably did not expect that.

Use:

def pair_finder(list1, list2, t):
 list1 = sorted(list1)
 list2 = sorted(list2)
 ...

The sorted(...) function doesn't modify the input list, and it returns a new list. By assigning those to the original variables, list1 & list2 will be sorted, but the caller's l1 & l2 lists won't be touched.

Pythonic Constructs

Loop like a native

List comprehension

l1 = []
for i in li.split(" "):
 l1.append(int(i))

This is an inefficient construct. You are creating a list, and then expanding the list one item at a time.

You could create the list all at once, using list comprehension:

l1 = [int(i) for i in li.split(" ")]

And applying the same operation to every item in a sequence is called a mapping operation, and Python has a built-in map(func, sequence) function:

l1 = list(map(int, li.split(" ")))

Or, combining with the input and using the better space handling:

print("Enter two space separated integer number sequences, of the same length.")
l1 = list(map(int, input("First sequence: ").split()))
l2 = list(map(int, input("Second sequence: ").split()))

Enumerate

 k = 0
 for j in list2:
 ...
 k += 1

This should be replaced with:

 for k, j in enumerate(list2):
 ...

to allow Python to maintain the k index while walking through the list2 items.

Extending Lists

Adding a list to another list is a list.extend(...) operation:

pairs = []
for q in pairs_low:
 pairs.append(q)
for w in pairs_high:
 pairs.append(w)
for r in pairs_equal:
 pairs.append(r)

Could become simply:

pairs = []
pairs.extend(pairs_low)
pairs.extend(pairs_high)
pairs.extend(pairs_equal)

if ... elif

 if i + j < t:
 ...
 if i + j > t:
 ...
 if i + j == t:
 ...

If the sum is less than t, it won't be greater than t, or equal to t. And if it is greater than t, it won't be equal to t. And if it is not less than or greater than t, it can only be equal to t. Why do the extra comparisons?

 if i + j < t:
 ...
 elif i + j > t:
 ...
 else:
 ...

PEP-8

Unnecessary parenthesis:

 elif (i + j == t_low):

Variable names too short to be meaningful

li, lj, l1, l1, q, w, r, t

Main guard

Mainline code should be protected with

if __name__ == '__main__':
 ...

to allow the file to be imported into another file, for unit tests, etc.

Algorithmic Improvements

pair_finder() starts off by sorting both input lists. That is an \$O(N \log N)\$ operation. Then it reverses one of the lists, which is an \$O(N)\$ operation. And then ...

for i in list1:
 ...
 for j in list2:
 ...

... which is \$O(N^2)\$! Right now, this is the time consuming part of the algorithm. But what are we doing? We are looking for two numbers which sum to target. Let’s turn that around:

for i in list1:
 desired = target - i
 # find "desired" in list2

Well, list2 is sorted, so we can do a binary search to find the desired value.

for i in list1:
 desired = target - i
 pos = bisect.bisect_left(list2, desired)
 ...

The binary search is \$O(\log N)\$, so with the outer loop, the time complexity has dropped to \$O(N \log N)\$, the same as the sorting.

The desired value may or may not be in list2. If it is, it is at list2[pos]. Assuming we don’t fall off the start of list2, then for the current i value, i+list2[pos-1] would be the largest sum less than target.

Assuming we don’t fall off the end of list2, if list2[pos] == desired, then the sum i+list2[pos+1] will be the smallest sum greater than target for the current value of i.

for i in list1:
 desired = target - i
 pos = bisect.bisect_left(list2, desired)
 if pos < len(list2):
 if list2[pos] == desired:
 # add (i, desired) to pairs_equal
 low, high = pos - 1, pos + 1
 else:
 low, high = pos - 1, pos
 if low >= 0:
 # add (i, list2[low]) to pairs_low, if >= t_low
 if high < len(list2):
 # add (i, list2[high]) to pairs_high, if <= t_high

But ... what about duplicates? If list2 contains duplicate values, pos + 1 may not be sufficient to advanced to a value larger than desired. You could use both bisect_left and bisect_right to find either end of a sequence of multiple desired values. The difference in right and left would be the count of those values, and you could add [(i, desired)] * count to pairs_equal. But you’d also need to do the same for the pairs_low and pairs_high, which means more binary searching to find those ends. Or, you could use two collections.Counter objects to count occurrences of each value in list1 and list2, and then remove duplicates values from list1 and list2. Any pairs added would need to be replicated by the product of the respective counts to occur the correct number of times in the result.

• Maarten Fabré: Excellent review. I would stick to the list comprehensions, instead of using map for clarity,