146. Two Sum II - Input Array Is Sorted

Because the array is sorted, start one pointer at each end. If their sum is too big, move the right pointer left to shrink it; if too small, move the left pointer right to grow it. The sorted order guarantees each move is safe.

Idea

The array is sorted, which lets two converging pointers find the pair in O(1) space (no hash map). Place lo at the start and hi at the end:

• If numbers[lo] + numbers[hi] equals target, done.
• If the sum is too large, the only way to decrease it is to move hi left (every element left of hi is ≤ it).
• If the sum is too small, move lo right to increase it.

Each step provably discards no valid pair, so the pointers meet at the answer.

Algorithm

1. lo = 0, hi = len - 1.
2. While lo < hi: compute s = numbers[lo] + numbers[hi]. If s == target return [lo+1, hi+1] (1-indexed); if s < target, lo += 1; else hi -= 1.

Worked example: numbers = [2,7,11,15], target = 9

• lo=0 (2), hi=3 (15): 2+15=17 > 9 → hi=2.
• lo=0 (2), hi=2 (11): 2+11=13 > 9 → hi=1.
• lo=0 (2), hi=1 (7): 2+7=9 → return [1, 2].

Complexity

• Time: O(n).
• Space: O(1) — satisfies the constant-space requirement.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0, hi = numbers.length - 1;
        while (lo < hi) {
            int sum = numbers[lo] + numbers[hi];
            if (sum == target) {
                return new int[]{lo + 1, hi + 1};
            } else if (sum < target) {
                lo++;
            } else {
                hi--;
            }
        }
        return new int[]{};
    }
}