Two Sum II

Given a sorted array, return the 1-indexed positions of the two numbers that add up to the target.

This is one of the cleanest first examples of opposite-end pointers.

It teaches how sorted input lets you remove huge parts of the search space safely.

Problem intuition

The sorted order is the whole unlock here. If the current sum is too small, only the left pointer can help. If it is too large, only the right pointer can help.

That monotonic movement makes the two-pointer solution both correct and optimal after you move past the brute-force baseline.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Brute force pair scan

O(n^2)O(1)

Check every pair until you find the matching sum. This is simple, but it ignores the fact that the array is already sorted.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[] {i + 1, j + 1};
                }
            }
        }

        return new int[] {-1, -1};
    }
}

Solution 2

Two pointers

O(n)O(1)

Use the sorted property directly. Move the left pointer when the sum is too small and the right pointer when the sum is too large.

class Solution {
    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[] {-1, -1};
    }
}