Two Sum II – Input Array Is Sorted

The array is sorted in non-decreasing order. Find the two positions i < j with a[i] + a[j] = target. Exactly one such pair exists. Positions are 1-based in this problem.

Input:

• line 1: n
• line 2: n sorted integers
• line 3: target

Output: i j (1-based, i < j).

Constraints: 2 ≤ n ≤ 10⁵, −10⁹ ≤ a[i], target ≤ 10⁹.

Challenge: the array is sorted, so you don't need a hash map: start one pointer at each end. If the sum is too small, move the left pointer right; if too big, move the right pointer left. O(n) time, O(1) memory.