Sweaty Imposter

Two Sum II (Sorted Array)

MediumTwo PointersNeetCode 150MidOpen on LeetCodeUpdated

You're given an array numbers sorted in non-decreasing order and an integer target. Find the two entries that add up to target and return their positions as [index1, index2], using 1-based indexing with index1 < index2. Exactly one valid pair exists. You may not use the same element twice, though two different elements can share a value. Use only constant extra space.

Examples

numbers = [2,7,11,15], target = 9 returns [1,2]

2 + 7 = 9. Counting from 1, those values sit at positions 1 and 2.

numbers = [2,3,4], target = 6 returns [1,3]

2 + 4 = 6, at positions 1 and 3. 3 + 3 would also make 6, but there is only one 3 and an element can't be used twice.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • Array is sorted ascending.
  • Exactly one solution exists.

Hints

Hint 1

The input is sorted, how can that let you avoid checking every pair?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Start one index at each end. If the pair sums to less than target, the left value is too small to pair with anything that remains, so move left forward; if it sums to more, the right value is too big, so move right back. Each step discards a value that can't be in the answer, so the unique pair is never skipped. Return both indices plus 1.

Time

O(n)

Space

O(1)

Pitfall

The answer is 1-based, so [2,7,11,15] with target 9 returns [1,2], not [0,1]. Keep the loop at left < right so one element is never paired with itself.

Solutions

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, 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 };
    }
}
Drill This