DEV Community

Youdiowei Eteimorde
Youdiowei Eteimorde

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode
twoNumberSum(array, targetSum)
[1, 4]
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode
pointerSum(array, targetSum)
[1, 4]
Enter fullscreen mode Exit fullscreen mode

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 []
Enter fullscreen mode Exit fullscreen mode
hashSum(array, targetSum)
[3, 2]
Enter fullscreen mode Exit fullscreen mode

Discussion (1)

Collapse
prishadavin profile image
PrishaDavin

Good information share with us!! Mohini vashikaran mantra for girl