Finding first pair of numbers in array that sum to value

Question

Im trying to solve the following Codewars problem: https://www.codewars.com/kata/sum-of-pairs/train/python

Here is my current implementation in Python:

def sum_pairs(ints, s):
    right = float("inf")

    n = len(ints)
    m = {}
    dup = {}

    for i, x in enumerate(ints):
        if x not in m.keys():
            m[x] = i # Track first index of x using hash map. 
        elif x in m.keys() and x not in dup.keys():
            dup[x] = i

        for x in m.keys():
            if s - x in m.keys():
                if x == s-x and x in dup.keys():
                    j = m[x]
                    k = dup[x]
                else:
                    j = m[x]
                    k = m[s-x]


                comp = max(j,k)
                if comp < right and j!= k:
                    right = comp


    if right > n:
        return None

    return [s - ints[right],ints[right]]

The code seems to produce correct results, however the input can consist of array with up to 10 000 000 elements, so the execution times out for large inputs. I need help with optimizing/modifying the code so that it can handle sufficiently large arrays.

Answer 1

Your code inefficient for large list test cases so it gives timeout error. Instead you can do:

def sum_pairs(lst, s):
    seen = set()
    for item in lst:
        if s - item in seen:
            return [s - item, item]
        seen.add(item)

We put the values in seen until we find a value that produces the specified sum with one of the seen values. For more information go: Referance link