Two Sum Sorted

medium LeetCode #167

two-pointers

Description

Given a 1-indexed sorted array of integers numbers and a target, find two numbers that add up to target. Return their indices as [index1, index2] where 1 <= index1 < index2.

Example 1:
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: 2 + 7 = 9. The indices are 1 and 2 (1-indexed).

Example 2:
Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Explanation: 2 + 4 = 6. The indices are 1 and 3.

Example 3:
Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Explanation: -1 + 0 = -1. The indices are 1 and 2.

Constraints

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

Complexity

Show Complexity

Time: O(n)
Space: O(1)

Hints

Show Hints

Pattern: Use two pointers: one at start, one at end
Approach: If sum > target, decrease right pointer. If sum < target, increase left pointer. Remember 1-indexed output!
Complexity: The array is sorted - use this property to avoid nested loops

Solutions

Show PY Solution

def solution(numbers, target):
    start = 0
    end = len(numbers) - 1

    while start < end:
        a = numbers[start]
        b = numbers[end]
        s = a + b
        if s == target:
            return [start + 1, end + 1]
        elif s < target:
            start += 1
        elif s > target:
            end -= 1

    return []