Two Sum II - Input Array Is Sorted

medium array two pointers binary search

Problem

Given a 1-indexed sorted array of integers and a target, return the 1-indexed positions of the two numbers that add up to the target. Each input has exactly one solution and you may not use the same element twice.

Inputnumbers = [2, 7, 11, 15], target = 9

Output[1, 2]

Two pointers l=0, r=n−1. If a[l]+a[r] > target → r−−; if < → l++; else found. Returns positions l+1, r+1.

sorted numbers (comma-separated)

target

def two_sum(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target: return [l + 1, r + 1]
        if s < target: l += 1
        else: r -= 1
    return [-1, -1]

function twoSum(numbers, target) {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    const s = numbers[l] + numbers[r];
    if (s === target) return [l + 1, r + 1];
    if (s < target) l++;
    else r--;
  }
  return [-1, -1];
}

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

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1;
    while (l < r) {
        int s = numbers[l] + numbers[r];
        if (s == target) return { l + 1, r + 1 };
        if (s < target) l++;
        else r--;
    }
    return { -1, -1 };
}

Explanation

The key gift here is that the array is already sorted. That lets us avoid a hash map entirely and instead race two pointers in from the ends, which uses no extra memory.

Put l at the first element and r at the last. Their sum s = numbers[l] + numbers[r] is one candidate. Because the array is sorted, moving l rightward can only make the sum bigger, and moving r leftward can only make it smaller.

So the rule is simple: if s == target we're done; if s < target we need more, so l++; if s > target we need less, so r--. Each step safely throws away a number that cannot be part of the answer.

Example: numbers = [2, 7, 11, 15], target = 9. Start 2 + 15 = 17 > 9, so r--. Now 2 + 11 = 13 > 9, so r-- again. Then 2 + 7 = 9, a match — return the 1-indexed positions [1, 2].

The pointers only move toward each other, so we touch each element at most once, giving a fast single pass.

Time: O(n) Space: O(1)