Two Sum (Part 2) Amazon Python Interview Question

You are given an array of integers nums sorted in non-decreasing order, meaning that each value is equal to or greater than the one before it.

Return the indices of the two values in nums that add up to a given target number.

Clarifications:

• There is at most one solution.
• If there is no valid solution, return [-1, -1].
• Return the indices in increasing order (i.e. [1,3], NOT [3,1]).

Your solution must use constant extra space. This means that the size of any objects that you create while solving the problem cannot grow with the length of nums. As a result, you won't be able to just use your solution from the original Two Sum problem.

Example #1

Input: nums = [1, 3, 4, 5, 7, 12, 15] , target = 9

Output: [2,3]

Explanation: The values at indices 2 and 3 (4 and 5, respectively) add up to 9.

A quick aside -- Memory Complexity

Remember that this problem requires constant extra space, so we can't just use the solution from the previous TwoSum problem.

In that problem, we used a dictionary to record the complement for each value we had already seen. This dictionary could potentially have as many entries as 1 fewer than the size of nums itself. This would not be constant extra space because the amount of memory needed to solve the problem is affected by the size of the inputs.

If you are creating a new array or dictionary, and each entry is related to an element in your input, then you are NOT using constant extra space! So we need to think of something different to solve this problem.

Intuition

When one of our inputs is already sorted it almost always means we can use this property to avoid extra work.

Taking the brute force approach first will often highlight where this extra work is occurring. Take the following test case:

nums = [1,3,4,5,7,12,15]; target = 9

Let's do a double nested for-loop to check each possible combination. We start with [1,3] , [1,4] ... and so on.

Once we reach [1,12] we know that no solution can possibly contain a 12, or 15.

This is because 1+12 > target. Here, 12 is paired with the smallest value in the array, so any other combination involving a 12 will also be greater than target. If this argument works for 12 then it certainly works for 15 which is even greater! So no solution could possibly have a 12, or 15.

We are eliminating options from the outside in. Here's a more formal way to express this intuition:

1. Take the left-most value (1) and the right-most value (15); these are the smallest and largest values, respectively. Add them up and call the result cur_sum.
2. cur_sum is the largest possible sum that you can make with a 1. So if cur_sum < target then the solution cannot possibly have 1 in it.
3. Conversely, cur_sum is also the smallest sum that you can make with a 15 in it. So if cur_sum > target then the solution cannot possibly have 15 in it.

If we have not yet found a match where cur_sum == target we will always be able to eliminate a value from the right or left until we find a match (or we conclude no such pair exists).

Code

The key is to start two pointers, one on each side of the array, and keep eliminating values from the outside in. Once the two pointers touch, we know we've considered the entire array and no such solution exists. If it did, we would have found it along the way.

This two-pointer method shows up quite often, so keep it in mind as you tackle other problems.

def sorted_two_sum(nums, target):
  left = 0
  right = len(nums)-1

  # Start at opposite ends
  # When the pointers meet, you have considered all options
  while right > left:
    cur_sum = nums[left] + nums[right]
    '''
    cur_sum is the greatest possible sum including left
    and the smallest possible sum including right
    '''
    if cur_sum == target:
      return [left, right]

    elif cur_sum < target:
      '''
      Highest possible sum including left is still less than target. 
      Therefore, eliminate left from consideration
      '''
      left = left+1
    elif cur_sum > target:
      '''
      Lowest possible sum including right is still greater than target. 
      therefore, eliminate nums[right] from consideration
      '''
      right = right-1

  return [-1,-1]