1. Two Sum

Description

See the description in the Two Sum question.

Solution

We need to find two numbers in the array that sum to the target value. The problem definition states "return indices of the two numbers such that they add up to target."

The wording made me think of x + y = target. But, when approaching problems, see if the equation can be rewritten that will make it easier to solve. In this case target - x = y.

When iterating through an array we will have the target value and the current item value (x). So, we want to find a value for y that solves the equation.

There are two approaches for finding y. One uses a cache, and the other uses two pointers. There is also a brute force solution of using nested loops, but it is too slow.

Cache Solution

I initially solved it using a cache. It is the easier of the two solutions for this question. In this solution, each element of the array is cached as the array is iterated over. It is then a matter of checking the array to see if y exists in it.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    cache = {}
    for i in range(len(nums)):
        diff = target - nums[i]
        if diff in cache:
            return [cache[diff], i]
        else:
            cache[nums[i]] = i
    return []

Two Pointer Solution

However, the problem can also be solved using two pointers. The two pointers method is used for solving the Three Sum problem.

1. Sort the array.

2. Initialize two pointers (left, right) to the first and last positions in the array.

3. Sum the values of the left and right elements.

   1. If the result is greater than the target value, then move the right pointer to the left (and hence resulting in a smaller sum the next time).

   2. If the result is less than the result, then move the left pointer needs to the right (resulting in a greater sum the next time).

4. Repeat step 3 until the summation equals the target. (The question states there will be one unique answer)

Example:

input = [11, 7, 4, 15], target = 18

1. sort the array: [4, 7, 11, 15]

2. initialize pointers: left = 0 (start of the array) right = 3

3. iterate through the array summing the left and right index values and moving the left and right pointers as appropriate:

iteration	left index	right index	sum
0	0	3	4 + 15 = 19
1	0	2	4 + 11 = 15
2	1	2	7 + 11 = 18

def twoSum(self, nums: List[int], target: int) -> List[int]:
    # enumerate returns an iterable object containing tuples of the index and value. We need to store the
    # original index of the value after the sorting is performed
    sortd = enumerate(nums)
    # now sort based on the value
    sortd = sorted(sortd, key=lambda x: x[1])
    left = 0
    right = len(sortd) - 1
    while left < right:
        # need position 1 here to get the value
        summ = sortd[left][1] + sortd[right][1]
        if target == summ:
            # need position 0 here to get the index. The min,max is done here to ensure
            # value is returned with the lowest position listed first.
            return [min(sortd[left][0], sortd[right][0]), max(sortd[left][0], sortd[right][0])]
        elif summ < target:
            left += 1
        else:
            right -= 1
    return []