DSAPrep
MediumTwo Pointers

Two Sum II Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.
View original on LeetCode ↗

This looks like Two Sum, but the array being sorted is the whole point: it means we don’t need a hash map to find the partner value, because we can reason about which direction to move using the order of the elements. That’s what unlocks the O(1)-extra-space requirement the problem asks for.

Brute Force

Time O(n²)Space O(1)

Ignore the fact that the array is sorted and check every pair, same as the original Two Sum. It’s guaranteed to find the unique pair, but it never uses the ordering information the problem hands us for free.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)
        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

Why it’s slow: it re-derives the same information a sorted array already gives us — for a sorted array we can tell instantly whether a candidate sum is too big or too small, but this approach throws that signal away and just brute-forces every pair.

Two Pointers (Converging)

OptimalTime O(n)Space O(1)

Put one pointer l at the start and one pointer r at the end. Because the array is sorted, the sum numbers[l] + numbers[r] moves in a predictable direction: if it’s too big, the only way to shrink it is to pull r left (every element left of r is <= numbers[r]); if it’s too small, the only way to grow it is to push l right. So at every step exactly one move is correct, and we never need to backtrack or remember anything beyond the two pointers.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            total = numbers[l] + numbers[r]
            if total == target:
                return [l + 1, r + 1]
            elif total < target:
                l += 1
            else:
                r -= 1
        return []

Tracing numbers = [1, 3, 4, 5, 7, 10, 11], target = 9:

l
1
0
3
1
4
2
5
3
7
4
10
5
r
11
6
sum = 12target = 9
1 / 6
comparingresult

1 + 11 = 12 > 9. Too big — move r left.

Correctness: if numbers[l] + numbers[r] > target, then pairing numbers[r] with anything to the right of l is even worse (the array is non-decreasing), so r is the only index that can safely move — and symmetrically for the too-small case. This means the converging scan can never skip past the true answer: whichever pointer would need to move to reach it is exactly the one the algorithm moves.

Complexity: l and r each move at most n times total and the loop stops as soon as they meet, so the whole array is scanned once → O(n) time. Only two index variables are kept → O(1) extra space, satisfying the problem’s constraint.