dee Caulcrick's blog

Problem: Find and return the indices of the two numbers in an array that sum up to the target number.

Example:

target = 9
arr = [2, 7, 11, 13]

Solutions

Brute Force

This involves iterating over each item in the array, finding the sum of the item and other individual items in the array and comparing it to the target.

This approach incolves a nested for loop which means a time complexity of O(n^2)

This is how it looks like in python:

my_list = [3, 2, 9, 8, 13, 7]

target = 9

#Brute Force Method

def two_sum(my_list, target):
    for i in range(len(my_list)):
        for j in range(i+1, len(my_list)):
            result = my_list[i] + my_list[j]
            if result == target:
                return [i, j]

two_sum(my_list, target) #Result: [1,5]

Using a Hashmap

This method involves passing each item through a hash function and storing it in a hashmap. Here's a step by step of how I solved this:

Create a hashmap
Find the difference of each item from the target value. The difference is the second value we need.
Check if the difference is already in the hashmap. If it isn't, add the number(not the difference) to the table, and move on to the next number in the list.
If the difference exists in the hash table, return its index and the index of the number in an array.

Now, let's see how it looks in code:

my_list = [3, 2, 9, 8, 13, 7]

target = 9

#Using a Hash Table

def two_sum(my_list, target):
    prevMap = {} #Create a Hashmap
    for i, n in enumerate(my_list):
        diff = target - n
        if diff in prevMap:
            return[prevMap[diff], i]
        prevMap[n] = i

two_sum(my_list, target) #Result: [1,5]

This method has a time complexity of O(n)

Two Sum Leetcode Problem

Solutions

Brute Force

Using a Hashmap