The two Sum problem

A popular array problem is the two sum problem. The problem states that given an array find two numbers that their sum is equal to a target value. There are several ways of solving this using:

• The naive approach
• Two pointer technique
• Hash maps

array = [1,2,3,4,5]
targetSum = 5

The naive approach

This technique involves using two for loops to iterate over the array to find the target sum. The time complexity for this method is O(n^2) and space complexity of O(1)

def twoNumberSum(array, targetSum):
    for i in range(len(array)):
        for j in range(len(array)):
            if array[i] + array[j] == targetSum and array[i] != array[j]:
                return [array[i], array[j]]
    return []

twoNumberSum(array, targetSum)
[1, 4]

The two pointer technique

This technique involves having two pointers one at the beginning of the array and one at the end of the array. If the value of both pointers is less than the target then move the left pointer to the right but if their is value is greater move the right pointer to the left.

Time Complexity is O(nlog(n)) and space complexity is O(1)

def pointerSum(arr, tar):
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] + arr[r] == tar:
            return [ arr[l], arr[r] ]
        if arr[l] + arr[r] < tar:
            l += 1
        if arr[l] + arr[r] > tar:
            r -= 1

    return []

pointerSum(array, targetSum)
[1, 4]

Hashmap technique

This technique stores the array in a hash map then uses the constant look up capability of hash maps to find the the corresponding two sum numbers.

def hashSum(arr, tar):
    hashmap = {}
    for i in range(len(arr)):
        hashmap[i] = arr[i]
        complement = tar - arr[i]
        if complement in hashmap.values() and complement != arr[i]:
            return [ arr[i], complement]
    return []

hashSum(array, targetSum)
[3, 2]