1
\$\begingroup\$

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)
\$\endgroup\$
4
  • \$\begingroup\$ What is the purpose of the code? \$\endgroup\$ Commented Jan 20, 2021 at 18:07
  • \$\begingroup\$ Btw you should tag this as python \$\endgroup\$ Commented Jan 20, 2021 at 19:22
  • \$\begingroup\$ I mean that you should just completely take the lst1 list out of the program and use a set instead. \$\endgroup\$ Commented Jan 20, 2021 at 19:29
  • 2
    \$\begingroup\$ Please replace the top image with a code block containing equivalent text. \$\endgroup\$
    – Reinderien
    Commented Jan 20, 2021 at 20:17

1 Answer 1

1
\$\begingroup\$

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) \$.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Correct answer in last example is [3, 7], not [5, 5] because 7 appears in the list of integers before second "5" \$\endgroup\$
    – Luca Brasi
    Commented Jan 20, 2021 at 19:13
  • \$\begingroup\$ You’re right, somehow I misread it. Nvm, all you need is to use a set instead of a list. Then it should work. \$\endgroup\$ Commented Jan 20, 2021 at 19:16
  • 1
    \$\begingroup\$ Thank you, I completely forgot about sets as distinct data types, remembered only function call, nevermind that :) \$\endgroup\$
    – Luca Brasi
    Commented Jan 20, 2021 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.