Two Sum (Part 2) Amazon Python Interview Question

You are given an array of integers 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 that add up to a given 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 . 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 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:

Let's do a double nested for-loop to check each possible combination. We start with and so on.

Once we reach we know that no solution can possibly contain a , or .

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

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

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

If we have not yet found a match where 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.