All Articles

Daily Coding Problem #1

Problem

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Solution

Brute-force

We can compute all combinations of 2 elements in the list and then verify if they adds up to k.

def solve(list_of_numbers, k):
    for index_1, element_1 in enumerate(list_of_numbers):
        for index_2, element_2 in enumerate(list_of_numbers):
            if index_1 != index_2:
                if element_1 + element_2 == k:
                    return True
    return False

This run in O(N²) due to the nested loop.

Using a set

As we iterate over the list we can store in a set the elements we’ve seen so far.

We can then check if weather or not we have seen the complement (difference with k) before.

def solve(list_of_numbers, k):
    seen = set()
    for element in list_of_numbers:
        complement = k - element
        if complement in seen:
            return True
        else:
            seen.add(element)
    return False

This run in O(N) since we iterate over the list once and lookup in a set is O(1).