Two Sum II Input Array Is Sorted

The problem

Given a list of integers numbers, sorted from smallest to largest, and an integer target, find the two numbers at different positions that add up to target. Return their two positions, counting from 1, with the smaller position first. The list may hold the same value more than once. Exactly one such pair exists.

What to write

function solve(numbers: number[], target: number): number[]

Input
numbers = [2,7,11,15]
target = 9

Output
[1,2]

Input
numbers = [-1,0]
target = -1

Output
[1,2]

Constraints

2 ≤ numbers.length ≤ 30000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list is sorted, and that fact is there to be used. There can be 30,000 numbers, so trying every pair is about 450 million additions. When a sum comes out wrong, the order tells you where the larger and the smaller numbers are.

2. Hint 2: Ask a smaller question

   Take 2, 7, 11, 15 with a target of 9. Could 15 be part of the answer? Pair it with the smallest partner it could have and look at the sum. What does that tell you about the largest number?

3. Hint 3: Name the pattern

   A sorted list and a pair to find are the signal. Put one pointer, a position you keep track of, on the smallest number and another on the largest, and add the two. Too large rules out the largest number; too small rules out the smallest. Closing in from both ends like this is opposing two pointers. Read the lesson on opposing two pointers.

4. Hint 4: State the invariant

   The pair you are looking for always lies between the two pointers, ends included. Every number you have stepped past is ruled out: even its best partner gave the wrong sum.

5. Hint 5: Sketch the pseudocode

   Count positions from 0. left = 0, right = last position. While left < right: sum = number at left + number at right. If sum equals target, return left + 1 and right + 1. If sum is smaller, add 1 to left. Otherwise subtract 1 from right.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Move inward from both ends; the sorted order tells you which pointer can bring the sum closer to the target.

The slow way

Try every pair of positions and return the pair whose numbers add up to the target. It is correct, but 30,000 numbers make about 450 million pairs, and the method never uses the one thing you were told about the list: that it is sorted.

The insight

Add the smallest and the largest number. If the sum is too large, the largest number is too large with every partner, because every other partner is at least as big as the smallest. So the largest can go. A sum that is too small removes the smallest number in the same way, and the question repeats on a shorter list.

Step by step

1. Start one pointer on the smallest number and one on the largest. A pointer is a position in the list, kept in a variable. In a sorted list the smallest and largest numbers sit at the first and last positions, and every candidate for the pair lies from one to the other.
2. Add the two numbers the pointers are on. This one sum is all a round needs: it either is the target or shows which of the two numbers can never be part of the pair.
3. The sum is the target: return both positions, counting from 1. The answer counts positions from 1 and the pointers count from 0, so each gets one added. The left pointer is always the smaller position.
4. Sum too small: move the left pointer one place to the right. The left number was added to the largest number not yet ruled out, and the sum was still too small. No other partner can do better, so the left number is ruled out.
5. Sum too large: move the right pointer one place to the left. The right number was added to the smallest number not yet ruled out, and the sum was still too large. Every other partner gives a sum at least as large, so the right number is ruled out.

The same numbered steps are the comments in each solution.

function solve(numbers, target) {
  // 1. Start one pointer on the smallest number and one on the largest
  let l = 0,
    r = numbers.length - 1;
  while (l < r) {
    // 2. Add the two numbers the pointers are on
    const sum = numbers[l] + numbers[r];
    // 3. The sum is the target: return both positions, counting from 1
    if (sum === target) return [l + 1, r + 1];
    if (sum < target) {
      // 4. Sum too small: move the left pointer one place to the right
      l++;
    } else {
      // 5. Sum too large: move the right pointer one place to the left
      r--;
    }
  }
  // The problem promises a pair, so this line is never reached.
  return [];
}

function solve(numbers: number[], target: number): number[] {
  // 1. Start one pointer on the smallest number and one on the largest
  let l = 0,
    r = numbers.length - 1;
  while (l < r) {
    // 2. Add the two numbers the pointers are on
    const sum = numbers[l] + numbers[r];
    // 3. The sum is the target: return both positions, counting from 1
    if (sum === target) return [l + 1, r + 1];
    if (sum < target) {
      // 4. Sum too small: move the left pointer one place to the right
      l++;
    } else {
      // 5. Sum too large: move the right pointer one place to the left
      r--;
    }
  }
  // The problem promises a pair, so this line is never reached.
  return [];
}

def solve(numbers, target):
    # 1. Start one pointer on the smallest number and one on the largest
    left, right = 0, len(numbers) - 1
    while left < right:
        # 2. Add the two numbers the pointers are on
        total = numbers[left] + numbers[right]
        # 3. The sum is the target: return both positions, counting from 1
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            # 4. Sum too small: move the left pointer one place to the right
            left += 1
        else:
            # 5. Sum too large: move the right pointer one place to the left
            right -= 1
    # The problem promises a pair, so this line is never reached.
    return []

Example 1, traced

Input
numbers = [2,7,11,15]
target = 9

Output
[1,2]

Why it works

The pair always lies between the two pointers, ends included. A pointer steps past a number only when that number gives the wrong sum even with its best partner, the one at the other pointer, so it cannot be half of the pair. A pair is promised, so the pointers land on it before they meet.

Time and space

Time O(n), extra space O(1). Each round either returns or moves one pointer one step closer to the other, so a list of n numbers takes fewer than n rounds: O(n) time. Only two positions and one sum are stored, whatever the length of the list: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Return positions that count from 1. The pointers count from 0, so add one to each. Forgetting this gives [0, 1] instead of [1, 2] on example 1.
• Move the correct pointer: left when the sum is too small, right when it is too large. With the two swapped, example 1 steps past the 2 in the first round, never finds the pair and returns an empty list.
• The hash map from Two Sum also works here, but it stores up to n numbers. The sorted order lets you find the pair while storing only two positions.

Pattern

Opposing two pointers. Builds on Two Sum and Valid Palindrome.

Keep going