Algorithm Challenge: Sum of Two

We’ll present an algorithm challenge and then provide two solutions: a runner-up and the optimal algorithm. Algorithms are written in Python.

The Challenge

Given two lists of integers, is there a set of numbers — one from each list — whose sum is equal to a specified value?

Here are two examples, one that would return True and the other that would return False.# Example returning True
list1 = [1,2,3,4]
list2 = [0,0,-1,4]
sumOfTwo(list1, list2, 8) # 4 + 4# Example returning False
list1 = [1,2,3,4]
list2 = [0,0,-1,4]
sumOfTwo(list1, list2, 9)

From the examples, you can see that both negative and positive values, as well as zero, are permitted values in either array. Our solution algorithm will return either True or False based on if there is a pair of values that add up to our third argument.

Runner-Up

The brute force method of solving this challenge is to loop through both lists in a nested fashion, looking for a pair whose sum is equal to our third value.def sumOfTwo(list1,list2,v):
 for a in list1:
   for b in list2:
     if a + b == v:
       return True
 return False

While this algorithm accurately gets us the desired output, nested for loops are generally inefficient and add unnecessary time complexity.

Optimal Solution

We can loop through each list independently, avoiding nested structures and reducing the time complexity of our algorithm. We’ll first loop through list1 and calculate the values we’re searching for in list2. Afterward, we iterate over list2 and see if any of the values belong in our created set.def sumofTwo(list1,list2,v):
 answers = set()
 for a in list1:
   answers.add(v - a)for b in list2:
   if b in answers:
     return True
 return False

Conclusion

We see from this algorithm challenge that nested loops should be avoided or refactored when possible. On a small scale, you may not feel the pain; however, the unnecessary time complexity will quickly compound as the lists grow.

I hope you liked this article! Subscribe to be notified when I publish new articles or even better, consider joining the medium community.