11.Two Sum II

MediumTwo Pointers · 2/5

Problem

You are given a 1-indexed array numbers sorted in non-decreasing order and an integer target. Find two numbers that add up to target and return their indices as [index1, index2] with 1 <= index1 < index2.

Exactly one solution exists, you may not use the same element twice, and your solution must use only constant extra space.

Examples

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: 2 + 7 = 9, at 1-indexed positions 1 and 2.

Input:  numbers = [2, 3, 4], target = 6
Output: [1, 3]
Explanation: 2 + 4 = 6.

Input:  numbers = [-1, 0], target = -1
Output: [1, 2]

Constraints

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
Exactly one solution exists.

💡 Key Insight

Sortedness gives direction. With pointers at the smallest (left) and largest (right) values, if numbers[left] + numbers[right] is too small, the only way to increase it is left++; if too large, right--. Each move permanently eliminates one element that cannot be part of the answer, so one O(n) sweep with O(1) space finds the pair.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Check every pair (i, j) with i < j. This ignores the sorted order entirely.

Algorithm

For i = 0..n-1, for j = i+1..n-1:
If numbers[i] + numbers[j] == target, return [i + 1, j + 1].

Visualization

numbers = [2, 3, 4], target = 6
i=0: 2+3=5 ✗, 2+4=6 ✓ → [1, 3]

Code

java

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

Complexity

Time: O(n²) — all pairs in the worst case.
Space: O(1).

Binary Search

TimeO(n log n)SpaceO(1).

Intuition

Fix the first element numbers[i]. Its partner must equal target - numbers[i] and must lie to the right of i. Because the array is sorted, binary search finds it in O(log n).

Algorithm

For each i:
- need = target - numbers[i].
- Binary search for need in numbers[i+1 .. n-1].
- If found at j, return [i + 1, j + 1].

Visualization

numbers = [2, 7, 11, 15], target = 9
i=0 (2): need 7, search [7, 11, 15]
         lo=1 hi=3 mid=2 → 11 > 7 → hi=1
         lo=1 hi=1 mid=1 → 7 found → [1, 2]

Code

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            int need = target - numbers[i];
            int lo = i + 1, hi = n - 1; // partner must be to the right of i
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == need) {
                    return new int[] {i + 1, mid + 1};
                } else if (numbers[mid] < need) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return new int[0];
    }
}

Complexity

Time: O(n log n) — one binary search per element.
Space: O(1).

Two PointersOptimal

TimeO(n)SpaceO(1)

Intuition

Start with left = 0 and right = n - 1. If the sum is too small, numbers[left] cannot pair with anything — even the largest remaining value was not enough — so discard it with left++. If the sum is too big, numbers[right] is too large even with the smallest remaining value, so right--. The answer is never skipped, and the pointers meet after at most n - 1 moves.

Algorithm

left = 0, right = n - 1.
While left < right:
- sum = numbers[left] + numbers[right].
- If sum == target, return [left + 1, right + 1].
- If sum < target, left++; else right--.

Dry Run

flowchart TD
    A["numbers = [2,7,11,15], target 9<br/>left=0, right=3"] --> B["2 + 15 = 17 too big"]
    B -->|"right--"| C["left=0, right=2<br/>2 + 11 = 13 too big"]
    C -->|"right--"| D["left=0, right=1<br/>2 + 7 = 9"]
    D --> E["return [1, 2]"]

Code

java

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}; // 1-indexed answer
            } else if (sum < target) {
                left++;  // need a larger sum
            } else {
                right--; // need a smaller sum
            }
        }
        return new int[0];
    }
}

Complexity

Time: O(n) — each step moves one pointer inward.
Space: O(1) — two indices.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Binary Search	O(n log n)	O(1)
Two Pointers	O(n)	O(1)

Common Pitfalls

Returning 0-indexed positions — this problem is 1-indexed.
Using a HashMap like the original Two Sum — it works but violates the constant-space requirement.
Moving the wrong pointer (e.g. left++ when the sum is already too large) — that throws away an element that may be part of the answer.
In binary search, searching the whole array instead of i + 1 .. n - 1 can return the same index i when need == numbers[i].