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?

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.