Two Number sum from an Array of Integers

An Introduction

This is a very common algorithm question. Although it sounds very easy at first while writing the code for such problems might trick you a little bit. This problem is commonly used in technical interviews and is a great way to demonstrate a programmer’s problem-solving skills. In this article, we will explore the problem in depth, discuss various approaches to solving it, and provide some tips on how to tackle similar algorithm problems.

Before we go to the solutions for each of these problems, let me explain the problem statement with an example. Also, this problem can be of summing 3 numbers, 4 numbers, etc. As the total count of numbers increases, complexity increases.

Solution – 1 – Brute Force Method

In this approach, we compare every pair of numbers in the array until we find the two numbers that add up to the target sum. This method has a time complexity of O(n^2) as it requires two nested loops to traverse the array.

At first, you are traversing the entire array for each of its elements and comparing the sum if it is equal to the given targetSum. The moment, it matches, breaks out inner and outer loops, and returns the result array.

# Time Complexity = O(n^2)
def twoNumberSum(array, targetSum):
    result = []
    for i in range(0, len(array),1):
        for j in range(i+1, len(array), 1):
            if array[i] + array[j] == targetSum:
                result.append(array[i])
                result.append(array[j])
                break
        if result != []:
            break
    return result

Solution – 2 [Better Solution]

The following is a better solution from a time complexity perspective. Instead of traversing the entire array for each element, traverse the array only once. For each number, calculate the expected second number needed in order to make the sum equal to targetSum. Now using, python’s built function check if that number exists in the array. If yes, then return those two values as an array. At last, if found nothing, an empty array will be returned.

# Time Complexity = O(n)
def twoNumberSum(array, targetSum):
    for iNum in array:
        expectedNum = targetSum - iNum
        if (expectedNum in array) and (expectedNum is not iNum):
            return [iNum, temp]
    return []