Two Sum II - Input Array Is Sorted

Given a sorted (non-decreasing) array of integers, find two numbers that add up to a given target. Return their 1-based indices. Exactly one solution exists, and you may not use the same element twice.

A hash map works but is unnecessary because the array is already sorted. Two pointers solve it in O(n).

Why this is worth learning

Sortedness lets one comparison discard a whole row or column of the pair search space. Without sorted input, the same pointer movement has no justification.

Before coding: one-minute experiment

For [1,2,4,8] and target 6, what is discarded after the first comparison, and what indices are returned?

Function signature

func TwoSumII(numbers []int, target int) []int

Inputs / outputs

• numbers: sorted integer slice.
• target: target sum.
• Return: a slice of two indices [i, j] (1-based, i < j).

Example

numbers = [2,7,11,15], target = 9
Output: [1,2]

Constraints

• 2 <= len(numbers) <= 100_000
• -1_000_000_000 <= numbers[i], target <= 1_000_000_000
• Exactly one solution exists.

Core idea (near-solution)

Use two pointers at the ends:

• If numbers[l] + numbers[r] is too small, move l right.
• If too large, move r left.
• If equal, return.

Invariant: all pairs outside [l, r] have already been ruled out.

Algorithm (step-by-step)

1. Set l = 0, r = len(numbers)-1.
2. While l < r:
   • Compute sum = numbers[l] + numbers[r].
   • If sum == target, return [l+1, r+1].
   • If sum < target, increment l.
   • Else decrement r.
3. (Unreachable if a solution is guaranteed.)

Correctness sketch

Assume every still-possible solution uses two indices within [l,r]. If numbers[l]+numbers[r] is below target, every pair using l and a smaller right endpoint has a sum no larger, so l cannot belong to a solution. If the sum is above target, every pair using r and a larger left endpoint has a sum no smaller, so r can be discarded. Equality gives a legal pair because l<r. Each discard preserves the possible solution promised by the contract and shortens the interval; eventually equality is found. Add one to both indices only when returning.

Trace (hand walkthrough)

Example input:
numbers = [2,7,11,15], target = 9
Output: [1,2]

Walk:
- l=0 (2), r=3 (15): sum=17 > 9 -> r=2
- l=0 (2), r=2 (11): sum=13 > 9 -> r=1
- l=0 (2), r=1 (7): sum=9 -> answer [1,2]

Pitfalls to avoid

• Returning 0-based indices instead of 1-based.
• Using the same element twice (l must be less than r).

Debugging lens

Use equal values at distinct positions, negative numbers, and a solution away from the endpoints. Verify the values through returned 1-based indices; returning the pair values is not sufficient.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Return a slice of length 2.

Reconstruction checkpoint

For [1,2,4,8] and target 6, what is discarded after the first comparison, and what indices are returned?

Return to Two Pointers · Module quiz