Two Sum / 2 Sum - Solution using Brute Force and Hash Table

Given an array of integers array, find two numbers such that they add up to a specific target number.

1
2
3
4
Input: [2, 7, 11, 15], target = 9
Output: 0, 1
Input: [5, 4, 17, 3], target = 7
Output: 1, 3

First Solution / Brute Force

• The first option is just to try all the pairs in the array and see if any of them add up to the number target.
• Since there are n2 possible pairs, this takes O(n2) time in the brute force.
• The solution uses only O(1) space since no extra space is used or created.
• This is not a “good” solution because better options exist, but it’s a correct solution.

1
2
3
4
5
6
def twoSum(array, target): 
    for i in range(len(array)):
        for j in range(i+1,len(array)):
            if array[i]+array[j]==target:
                return [i,j] 
    return []

Fast Solution / Optimized Solution

• Better than the above option is to create a dictionary (hash table) of all the elements in the array.
• Now you can scan over the array and check, for each element num(array[i]), whether there’s another element remainder(array[j]) where remainder = target - num is present in the dictionary, then return pair which add up to the target.
• This one runs in expected time O(n) because n insertions and n lookups in a dictionary take expected time O(n).
• It uses space O(n). This is considered a “good” solution

1
2
3
4
5
6
7
8
9
def twoSum(array, target):
    values = {}
    for i, num in enumerate(array):
        remainder = target - num 
        if remainder in values: 
            return [i, values[remainder]] 
        else: 
            values[num] = i 
    return []

These solutions are very common, you can find more solutions like sort binary search, sliding windows, etc.

Thank you.