Two Sum II - Sorted

Problem

You are given a 1-indexed array of integers numbers that is sorted in nondecreasing order, and an integer target.

Return the 1-indexed positions of the two numbers such that they add up to target.

The input has exactly one solution, and you may not use the same element twice.

Intuition

The array is sorted, which changes everything.

If the current sum is too small, moving the left pointer right can only increase it. If the current sum is too large, moving the right pointer left can only decrease it. That monotonicity gives us a deterministic search path instead of trying every pair.

This is the cleanest possible two-pointer setup: one pointer starts at each end, and each comparison tells you exactly which direction to move.

Approach

use std::cmp::Ordering;

impl Solution {
    pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
        let mut left = 0usize;
        let mut right = numbers.len() - 1;

        while left < right {
            let sum= numbers[left] + numbers[right];

            match sum.cmp(&target) {
                Ordering::Less=> left = 1,
                Ordering::Greater=> right -= 1,
                Ordering::Equal=> {
                    return vec![(left + 1) as i32, (right + 1) as i32];
                }
            }
        }

        unreachable!("the problem guarantees exactly one solution");
    }
}

function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

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

    if (sum < target) {
      left++;
    } else if (sum > target) {
      right--;
    } else {
      return [left + 1, right + 1];
    }
  }

  throw new Error("the problem guarantees exactly one solution");
}

Trace

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

The search is linear because each pointer only moves inward.

Edge cases

• Negative numbers work the same way; sorted order still gives monotonic movement.
• Minimal array length is still valid because the problem guarantees one solution.
• Duplicate values do not require special handling when the solution is unique.

Takeaway

Sorted order turns pair search into geometry.

Once the data is monotone, a single comparison tells you which half of the search space can be discarded forever. That is why two pointers are such a strong fit for sorted arrays.