4.5.2 — Two Sum II: Input Array Is Sorted

LeetCode 167 · Medium

The problem

The array is sorted. Find the two numbers adding to target and return their positions, 1-indexed. Exactly one answer exists, and you must use O(1) extra space.

numbers = [2, 7, 11, 15], target = 9   →  [1, 2]
numbers = [2, 3, 4],      target = 6   →  [1, 3]

Two details decide the solution. The array is sorted, which is the gift. And the space must be O(1), which rules out the hash map from 4.4.3.

The pattern

Put one pointer on the smallest value and one on the largest. Add them.

• Sum too small? The only way to grow it is to move the left pointer right, because everything to the right is larger.
• Sum too big? Move the right pointer left.
• Equal? Done.

Each step throws away a whole set of possibilities without checking them one by one.

Why discarding is safe

This is the part worth understanding, because the same argument justifies every two-pointer solution in this chapter.

Suppose numbers[l] + numbers[r] < target. Ask what numbers[l] could still pair with. Its largest possible partner is numbers[r], since the array is sorted and r is the far end. If even that partner is too small, then numbers[l] cannot reach the target with anything. It is finished. Move past it.

The mirror argument covers the too-big case. So each move eliminates one element permanently, and no move ever needs to be undone.

That shape — this element cannot be part of any answer, so discarding it is safe — is the proof behind two pointers everywhere. If you cannot make that argument for a problem, two pointers is the wrong tool.

The solution

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            total = numbers[l] + numbers[r]
            if total == target:
                return [l + 1, r + 1]     # the problem is 1-indexed
            if total < target:
                l += 1
            else:
                r -= 1
        return []

TypeScript

function twoSum(numbers: number[], target: number): number[] {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    const total = numbers[l] + numbers[r];
    if (total === target) return [l + 1, r + 1];
    if (total < target) l++;
    else r--;
  }
  return [];
}

The + 1 on the return is the only thing here that trips people up. The problem indexes from 1.

Complexity

O(n) time and O(1) space. The two pointers together cover the array once, since each step moves exactly one of them and they never move apart.

Compare with binary search, which would be O(n \log n): for each element, binary search for its partner. Two pointers is strictly better because it reuses the work from the previous comparison instead of starting a fresh search each time.

Two pointers or a hash map?

the input is	you must return	use
sorted	anything	two pointers, O(1) space
unsorted	indices into the original array	hash map
unsorted	values only, memory tight	sort first, then two pointers

Sorting an unsorted array to use two pointers destroys the original indices, which is exactly why 4.4.3 cannot use this method.

Where this goes next

This is the engine inside larger problems. Fix one element and run this on the rest, and you have 3Sum. Fix two and you have 4Sum. That is 4.5.3.

Next: 4.5.3 3Sum — this loop wrapped in another loop, where all the real difficulty turns out to be duplicate handling.