Is the sum of 2 numbers in list k

Question

I got a coding problem to solve and was wondering if I got a commonly acceptable and efficient/clean solution. If there is a better way I'd gladly hear it.

given a list with numbers return if the sum of 2 elements in the list = k

def is_sum_of_2nums_in_list_k(list, k):
 for i in list:
 if k - i in list:
 return True
 return False

They also mentioned you get bonus points if you do it in one 'pass'. What does this mean?

• RisingSun: that seems to be very efficient and will finish in one pass. They just dont want you to iterate over the list multiple times.
• Carcigenicate: I think this would require multiple passes. in is O(len) for lists afaik. In the worst case, both the for and in will do a full pass. If list was a set, this would be much more efficient.
• Bas Velden: @Carcigenicate If I understand correctly, a pass is a full iteration over the list. If that is the case, how would I do this in one iteration? (from what I understand in also iterates, meaning I iterate twice in my given solution)
• Carcigenicate: Yes, a "pass" over a list means an iteration over it. And I'm not sure of an algorithm off the top of my head. If you were allowed to start with a set instead of a list, your function would already work, but that likely isn't an option. You could try doing something like having a local set, and you add each difference to it as you find them. I'm not sure if that would work though. I can see a couple problems with that.

Answer 1

You are using one explicit pass over the list (for i in list), and one implicit pass over the list (k - i in list). This means your algorithm is \$O(N^2)\$.

Note: You can reduce your implementation to one line:

return any(k - i in list for i in list)

But you have a bug. is_sum_of_2nums_in_list_k([5], 10) returns True.

A one pass algorithm

• starts with an empty set,
• takes each number in the list,
  • tests if k-i is in the set,
    • return true if it is,
  • adds i to the set.
• returns false

Answer 2

(Quick note: please do not use list as a variable name, as it's also the name of a type. I'm going to use list_ instead)

Depending on the interpretation, it could be that they want you to iterate over the list just once.

The statement "v in list" potentially iterates over the full list, which means it's yet another pass.

If you know nothing about the list, except that they are numbers, one approach would be to store the values seen so far in a set, which has a more efficient "in".

def is_sum_of_2nums_in_list_k(list_, k):
 seen = set()
 for i in list_:
 if k - i in seen:
 return True
 seen.add(i)
 return False

This works the same as your initial solution, but for each new number, it only checks if the sum of that number and an earlier number add up k.

As a downside: storage needs to be allocated for the set seen, so this does not work with constant memory.

If on the other hand, we have also been told that the list was ordered, we can go for a different approach

def is_sum_of_2nums_in_list_k(list_, k):
 # Assumption: `list_` is ordered.
 left, right = 0, len(list_) - 1
 while left < right:
 total = list_[left] + list_[right]
 if total == k:
 return True
 if total < k:
 left += 1
 if total > k:
 right -= 1
 return False

This is a bit more complicated, but requires constant extra storage.