3.18 Two Sum II - Input Array Is Sorted

3.18.1 Problem Metadata

3.18.2 Description

Given a 0-indexed array numbers that is sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the 1-indexed positions [index1, index2] where 0 <= index1 < index2 < numbers.length. Exactly one valid answer exists, and each element may be used at most once.

3.18.3 Examples

Example 1

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: numbers[0] + numbers[1] = 9, so we return indices shifted by one.

3.18.4 Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • -1000 <= target <= 1000
  • numbers is sorted in non-decreasing order
  • Exactly one solution exists

3.18.5 Solution - Two Pointers

3.18.5.1 Walkthrough

Use two indices, left at the start and right at the end of the array. Compare numbers[left] + numbers[right] with the target and shrink the window from the side that makes the sum move toward the target. Because the array is sorted, moving the pointers monotonically guarantees we visit each pair at most once.

3.18.5.2 Analysis

  • Time Complexity: O(n) - Each pointer moves at most numbers.length steps
  • Space Complexity: O(1) - Only uses two pointer variables

Key Insight: Sorted order enables a monotonic sweep—moving left only increases the sum, moving right only decreases it—so every pair is considered once with constant extra space.

3.18.5.3 Implementation Steps

  1. Initialize left = 0, right = numbers.length - 1.
  2. While left < right:
    1. Let current = numbers[left] + numbers[right].
    2. If current == target, return [left + 1, right + 1].
    3. If current < target, increment left to increase the sum.
    4. Otherwise, decrement right to decrease the sum.
  3. Return an empty array (the problem guarantees this branch is unreachable).

3.18.5.4 Code - Java

public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];

        if (sum == target) {
            return new int[]{left + 1, right + 1};
        }

        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[0];
}

3.18.6 Solution - Binary Search

3.18.6.1 Walkthrough

Treat each numbers[i] as the first addend and binary-search for target - numbers[i] in the suffix [i + 1, n). The array is sorted, so binary search can find complements in logarithmic time, and searching only in the suffix ensures we never reuse the same element or produce reversed indices.

3.18.6.2 Analysis

  • Time Complexity: O(n log n) - one binary search per element, shrinking search range as i grows
  • Space Complexity: O(1) - constant extra pointers

When to use: This is a clear, deterministic alternative to two pointers when you want per-element searches or need a pattern that generalizes to other lookup-style problems. It trades a small slowdown (log factor) for a simple inner loop.

3.18.6.3 Implementation Steps

  1. Loop i from 0 to numbers.length - 2.
  2. Set complement = target - numbers[i].
  3. Binary search for complement in [i + 1, numbers.length).
  4. If found at j, return [i + 1, j + 1].

3.18.6.4 Code - Java

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length - 1; i++) {
        int complement = target - numbers[i];
        int j = binarySearch(numbers, i + 1, numbers.length - 1, complement);

        if (j != -1) {
            return new int[]{i + 1, j + 1};
        }
    }

    return new int[0];
}

private int binarySearch(int[] numbers, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (numbers[mid] == target) {
            return mid;
        } else if (numbers[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}