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).

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

• Invariant: all pairs outside [l, r] have already been ruled out.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

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).

Complexity

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

Implementation notes (Go)

• Return a slice of length 2.