Two Sum Leetcode Problem

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

Example:

python
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:

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:

1. Create a hashmap
2. Find the difference of each item from the target value. The difference is the second value we need.
3. 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.
4. 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:

python
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)