Given an integer s and a list of integers ints finding (x,y) in ints such that s = x + y

Question

The following function sum_pairs(ints, s) takes two inputs: ints is a list with integer values and s is a integer number. The function sum_pairs returns the values (x, y) in ints such that \$s = x + y\$ and the index of y is the lowest for the (x, y) in ints such that \$s = x + y\$. This is a problem taken from codewars. The function passes all the test cases. However, when I attempt to run the code for a big list, the server codewars gives me the following answer: "Process was terminated. It took longer than 12000ms to complete".

I am wondering whether the code I have written to solve the problem can be optimised or should I use a different approach to give a solution.

def sum_pairs(ints, s):

    begin = 1
    end = len(ints)
    memo = []

    while begin < end:
        try:
            memo.append([begin-1, ints.index(s - ints[begin-1], begin, end)])
            begin += 1
            end = memo[-1][1]
        except:
            begin +=1

    if memo == []:
        return None
    else:
        return [ints[memo[-1][0]], ints[memo[-1][1]]]

The function sum_pairs(ints, s) searches for \$y = s - x\$ in the list ints using the function index(). If a value of y is found the index for the pair (x,y) is added to memo, then the range for the search (begin, end) are updated. Else only the lower limit begin for the search is updated.

Answer 1

Your code takes too long, because to check if a number is in array you use .index, effectively iterating over the whole array. However, since you need lots of these lookups, you can speed them up with more suitable data structure - set will do:

def sum_pairs_lookup(ints, s):
  waiting_for_pair = set()
  for y in ints:
    if (s - y) in waiting_for_pair:
      return [s - y, y]
  waiting_for_pair.add(y)

Also instead of looking for corresponding y, you can look for corresponding x, starting from the array's beginning. In this case the first match would give you the result.

Run it online

Edit: changed to accomodate points raised in comments, current version passes tests

Answer 2

Your code's complexity is \$O(n^2)\$, this means that worst case it's on-par with looping through ints in a nested loop, and returning the maximum for x, or the minimum for y. And so it's on-par with:

def sum_pairs(ints, s):
    try:
        return max(
            (x, y)
            for x in ints
            for y in ints
            if x + y = s
        )
    except ValueError:
        return None

You could speed this up, if ints is sorted, which your code implies, then you could change max to next, and flip the x and y. However, this still has \$O(n^2)\$ time.

The simplest way to force \$O(n)\$ time is to use a deque, and consume both ends of the sorted deque. This works by removing the tail of the deque to the point that \$x + y \le s\$. After this if \$x + y = s\$, then we return that. If not we take the next item at the head of the deque. Something like:

from collections import deque


def sum_pairs(ints, s):
    q = deque(ints)
    try:
        while True:
            y = q.popleft()
            n = s - y
            while q[-1] > n:
                q.pop()
            if q[-1] == n:
                return q[-1], y
    except IndexError:
        return None

Answer 3

To expose more the logic, this is a list version code of the @Daerdemandt idea. Two lines shorter but not as fast as as it was required:

def sum_pairs(ints, s):
    for i in range(1,len(ints)):
        if (s - ints[i]) in ints[0:i]:
            return [s - ints[i], ints[i]]