Optimizing solution of Sum of Pairs: Codewars in Python

Question

enter image description hereI need help to optimize my code for huge lists with approx. 10000000 elements. Is there a way to improve my algorithm or should I try to build a new one using a completely different approach? Task: given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

def sum_pairs(ints, s):
 lst1 = []
 for n in ints:
 if n in lst1:
 return [s-n, n]
 lst1.append(s-n)
lst3 = list(range(1,10000000))
sum_pairs(lst3, 20000000)
*Times out :(
#Using set() every time we add new item to the list doesn't help
def sum_pairs(ints, s):
 lst1 = []
 for n in ints:
 lst2 = set(lst1)
 if n in lst2:
 return[s-n, n]
 lst1.append(s-n)

• Ted Brownlow: What is the purpose of the code?
• my_stack_exchange_account: Btw you should tag this as python
• my_stack_exchange_account: I mean that you should just completely take the lst1 list out of the program and use a set instead.
• Reinderien: Please replace the top image with a code block containing equivalent text.

Answer 1

You could use a set as lst1 instead of a list. Every time you check if n is in lst1, it’s \$ O(n) \$ time complexity. Using a set instead will lower that to \$ O(1) \$.

• Luca Brasi: Correct answer in last example is [3, 7], not [5, 5] because 7 appears in the list of integers before second "5"
• my_stack_exchange_account: You’re right, somehow I misread it. Nvm, all you need is to use a set instead of a list. Then it should work.
• Luca Brasi: Thank you, I completely forgot about sets as distinct data types, remembered only function call, nevermind that :)