LeetCode 167 · Medium · Two Pointers

Two Sum II: Input Array Is Sorted

Given an array numbers sorted in ascending order and a target, return the 1-based positions of the two numbers that add up to the target, using only constant extra space.

O(n)time
O(1)space
2 endsdrop a value each step

numbers: 2–16 integers in ascending order, −999 to 999 · target: −1998 to 1998

Legend outline = numbers[l..r], the only values that can still be in the answer · index labels are 1-based

public int[] twoSum(int[] numbers, int target) { int l = 0; int r = numbers.length - 1; while (l < r) { int cur = numbers[l] + numbers[r]; if (cur > target) { r--; // numbers[r] is too big for anyone } else if (cur < target) { l++; // numbers[l] is too small for anyone } else { return new int[]{l + 1, r + 1}; } } return new int[0];}
l
—
r
—
cur
—
target
—
dropped
0

Why it works

  1. Brute force tries every pair: O(n²). The hash map from Two Sum is O(n) time but O(n) space, and ignores that the input is sorted.
  2. Each comparison rules out a whole value. If numbers[l] + numbers[r] is too big, numbers[r] is too big even with the smallest value left, so it pairs with nothing: drop it. Too small mirrors that for numbers[l]. The answer always stays inside [l, r].
  3. Why O(n): every step moves one pointer inward, so there are at most n − 1 steps. Two indices are all the memory used.
  4. Pitfall: the answer is 1-based. Return [l + 1, r + 1], not [l, r].
  5. Related: 3Sum fixes one value and runs exactly this loop on the rest; Container With Most Water uses the same "drop the side that cannot help" argument.