Pair with Target Sum in Sorted Array

You are given an array of n integers sorted in non-decreasing order and an integer target. Find the 1-indexed positions of two distinct elements in the array whose values sum exactly to target. It is guaranteed that exactly one such pair of positions exists. Report the two positions in increasing order.

Input: The first line contains the integer n. The second line contains n space-separated integers representing the sorted array. The third line contains the integer target. Output: Print two space-separated integers: the 1-indexed positions of the two elements that sum to target, in increasing order.

2 <= n <= 10^5 -10^9 <= arr[i] <= 10^9 arr is sorted in non-decreasing order -10^9 <= target <= 10^9 Exactly one valid pair of indices exists

Sortedness is exactly what allows this DIRECTIONAL elimination - without it, you couldn't confidently decide which pointer to move, since a random unsorted array gives no guarantee about what moving a pointer would do to the sum.

Find two positions in a sorted array whose values add up to a target, using two pointers moving inward. Brute force: Check every possible pair of positions directly with two nested loops - this costs O(n²), unnecessary given the array's sorted structure. Optimised: Since the array is sorted, moving pointers inward from both ends lets you ELIMINATE one element every single step (whichever pointer's adjustment direction is determined by comparing the current sum to the target) - this achieves the same result as checking every pair, but in linear time instead of quadratic.

1. Start one pointer at the FRONT of the array, one at the BACK. 2. If the sum at the two pointers is TOO SMALL, move the LEFT pointer right (to increase the sum); if TOO LARGE, move the RIGHT pointer left (to decrease it). 3. Stop as soon as you find the exact sum - the guarantee of a unique pair means no further searching is needed.

Time: O(n) - both pointers move inward monotonically, meeting after at most n total steps. Space: O(1) - just two pointer variables.

Handle n = 2 (the only possible pair is (1,2)). The required pair may involve elements deep inside the array rather than the extremes, and an O(n) two-pointer scan is required to stay within time limits at n = 10^5.

This is the most foundational two-pointer problem - be ready to state the movement rule (sum too small, move left right; sum too big, move right left) instantly, since it's the template for nearly every other two-pointer problem on sorted arrays.