2sum

Given an array of random elements and a target [1,-8,12,3,6,-2,4], 10 You are to write an algorithm to get the target from two of the elements of the given array and return their respective index as an sorted array.

target = 10
nums = [1,-8,12,3,6,-2,4]

output = [4,6]

First solution - Naive approach

To start we iterate of the array once to get the first element of the two. Meaning we will have a pointer from the beginning of the array to the end of the array.

for i in range(len(nums)):
    first_number = nums[i]
    print(first_number)

This approach means that we take the first element of the array. Adding another iteration to look for another element of the array is a bit more complicated since we have to take care of the two pointers and what they are looking at. First iteration, we need to take care of that the last element will be looked at from the second iteration. But how do we combine the two?

But how do we combine the two?

We combine the iterations by having the first index going into the second iterations. Meaning the second iterations starts of where the first iteration start plus one index forward.

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):

First pointer i starts from the beginning, but since we now have a second pointer j also looping through the array; this j will go all the way to the end. However the first pointer does not need to go to the end of the array since we have j taking care of that now.

# first iteration will start in the beginning
# i ends at next last element
nums = [1,-8,12,3,6,-2,4]
        i,...,       i

for i in range(len(nums) - 1):


# j goes from the pointer of i upto the end of the array
nums = [1,-8,12,3,6,-2,4]
           j,...,      j

    for j in range(i + 1, len(nums)):

The whole operation with checking if the two elements actually match for the target can now be calculated given the looping of the array; as we are now iterating over each possible outcome of the array.

# O(n)
for i in range(len(nums) - 1):
    # O(n)
    for j in range(i + 1, len(nums)):
        if (nums[i] + nums[j]) == target:
            return [i,j]
return []

Time and space complexity of the algorithm is n^2 due to the fact that we have a nested for loop of the entire array, but no external variables that we are saving.

time: O(n^2) space: O(1)

Second approach

What if we could reduce the time but use some more space? This is where we will be using a hashmap of the values that we have seen already to calculate the missing element we would want in order for us to get to the target given the current element we are on.

seen_nums = {}

for i in range(len(nums)):
    diff = target - nums[i]

    if diff in seen_nums:
        return [seen_nums[nums[i]], i]
    if nums[i] not in seen_nums:
        seen_nums[nums[i]] = i

return []

TODO:

write the two pointer method and the hash method

# data-structures

Data structures and algorithms - 2sum

Introduction to Algorithms