Two Sum II - Input Array Is Sorted

MediumTwo Pointers · Sorted Array🧩 Two Pointers LeetCode #167 ↗Updated Oct 30, 2026

Problem

The array numbers is sorted in non-decreasing order. Find two different positions whose values add up to target and return them as 1-based indices [i, j] with i < j. Exactly one answer exists, and you may use only constant extra space.

Input[2,7,11,15], target=9Output[1,2]

Input[2,3,4], target=6Output[1,3]

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

2 ≤ n ≤ 3·10⁴ · -1000 ≤ numbers[i], target ≤ 1000 · exactly one solution · O(1) extra space

Try it yourself

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

With the array sorted, the pair sum is monotonic in each pointer: too small → move the left pointer right, too big → move the right pointer left. Each move safely discards one element forever.

PatternTwo Pointers

Instinct Sorted input, a pair/triple hitting a target, or something symmetric? Put one pointer at each end and move the one that can only improve things.

Memory hack Squeeze from both ends - every step throws away a whole row of the brute-force grid.

Open the Two Pointers guide →

Approaches

Brute ForceCheck Every Pair

Time O(n²)Space O(1)

Try every pair (i, j) with i < j. Sorting lets us break the inner loop once the sum exceeds the target, but the worst case is still quadratic.

Java

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) return new int[]{i + 1, j + 1};
            if (sum > target) break; // sorted: only grows from here
        }
    }
    return new int[]{};
}

Trivially correct, ignores most of the sorted-order information.

BetterBinary Search the Complement

Time O(n log n)Space O(1)

Fix numbers[i]; the partner must equal target - numbers[i]. Because the array is sorted, binary search for it in [i+1, n-1] — searching only to the right avoids reusing i.

Java

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int need = target - numbers[i];
        int lo = i + 1, hi = numbers.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (numbers[mid] == need) return new int[]{i + 1, mid + 1};
            if (numbers[mid] < need) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return new int[]{};
}

Uses the sort order and O(1) space, but still pays a log factor per element.

OptimalTwo Pointers from Both Ends

Time O(n)Space O(1)

Start with l = 0, r = n-1. If the sum is too small, numbers[l] can't pair with anything (its largest partner already failed) → l++. If too big, numbers[r] is useless → r--. The answer pair is never skipped.

Java

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++;  // need a bigger sum
        else right--;              // need a smaller sum
    }
    return new int[]{};
}

Dry run[1,3,4,5,7,11], target=9

l leftr right changed

1
1
l
3

4

5

7

11
r
1+11=12 > 9 → r--
2
1
l
3

4

5

7
r
11

1+7=8 < 9 → l++
3
1

3
l
4

5

7
r
11

3+7=10 > 9 → r--
4
1

3
l
4

5
r
7

11

3+5=8 < 9 → l++
5
1

3

4
l
5
r
7

11

4+5=9 → [3,4] ✔

Linear time, constant space — the expected answer.

Pro tip

Values are tiny here, but with large ints compute the sum as long to avoid overflow.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Pair	`O(n²)`	`O(1)`
Better	Binary Search the Complement	`O(n log n)`	`O(1)`
Optimal	Two Pointers from Both Ends	`O(n)`	`O(1)`

Common pitfalls

Returning 0-based indices — the problem wants 1-based.
Using a HashMap like Two Sum I — works but violates the O(1) space rule.
Binary search over the whole array can return i itself (e.g. 3+3=6).

Interview tips

Explain why discarding l or r is safe — that is the proof.
Contrast with Two Sum I: unsorted → hash map; sorted → two pointers.
This loop is the inner engine of 3Sum / 4Sum — say so.

Pattern

Opposite-end two pointers → pair search in a sorted array where the sum moves monotonically.

My notes saved in this browser