Two Sum II - Input Array Is Sorted

Problem

You are given a 1-indexed array numbers, sorted in non-decreasing order, and a target integer. Exactly one pair of elements at distinct positions sums to the target. Return their 1-based indices [i, j] with i < j.

Two constraints distinguish this from plain Two Sum: the input is already sorted, and the solution must use O(1) extra space, which rules out a hash map.

Examples

Example 1

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

numbers[1] + numbers[2] = 2 + 7 = 9 (1-indexed).

Example 2

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

2 + 4 = 6. Note [2, 2] would be invalid — the same element can’t be used twice.

Example 3

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

-4 + -1 = -5. Negative values do not change the method.

Constraints

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000, -1000 <= target <= 1000
• numbers is sorted in non-decreasing order.
• Exactly one solution exists; O(1) extra space is required.

Think about it first

TL;DR

Converging two pointers from both ends — O(n) time, O(1) space.

Approach 1 — Brute force

Try every pair of positions.

from typing import List

def twoSum(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 []

Complexity: O(n^2) time, O(1) space. At n = 3 * 10^4 that is about 4.5 * 10^8 pair checks, too slow, and it ignores the sorted order entirely.

Approach 2 — Fix one element, binary search the complement

The insight: the array is sorted, so once you fix numbers[i], its required partner target - numbers[i] can be found (or ruled out) in O(log n) with binary search, which compares the middle element and discards the half that cannot contain the key.

from typing import List

def twoSum(numbers: List[int], target: int) -> List[int]:
    n = len(numbers)
    for i in range(n):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1          # search strictly to the right of i
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i + 1, mid + 1]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

Walkthrough on numbers = [2, 3, 4], target = 6:

1. i = 0 (value 2), need = 4. Search in indices 1..2: mid = 1 gives 3 < 4, so lo = 2; mid = 2 gives 4 == 4, return [1, 3].

Searching only to the right of i is what prevents using the same element twice.

Complexity: O(n log n) time, O(1) space. Accepted, but a factor of log n slower than necessary.

Approach 3 — Converging two pointers

The insight: put pointers at both ends. The pair (left, right) is the current candidate. Because the array is sorted, a too-small sum rules out numbers[left]: it was just paired with the largest value still in range, and every remaining partner is smaller, so left advances. Symmetrically, a too-large sum rules out numbers[right], so right moves in. Every comparison eliminates one element, so at most n - 1 steps reach the unique answer, with no extra memory and no inner search.

flowchart TD
    A["Compute sum = numbers[left] + numbers[right]"] --> B{Compare sum to target}
    B -->|sum == target| C["Return [left+1, right+1]"]
    B -->|sum < target| D["left += 1"]
    B -->|sum > target| E["right -= 1"]
    D --> A
    E --> A

from typing import List

def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []          # unreachable: a solution is guaranteed

Walkthrough on numbers = [2, 7, 11, 15], target = 9:

Complexity: O(n) time, O(1) space.

Common pitfalls

• Returning 0-based indices: the problem is 1-indexed, so both positions need the + 1.
• Moving the wrong pointer: the argument only works one way. A small sum rules out left, a large sum rules out right. Swapping them breaks correctness, not just speed.
• Using a hash map: it works but uses O(n) space, which violates the stated constraint.
• Binary searching the whole array instead of i+1..n-1: you may find i itself when need == numbers[i], reusing one element.

Pattern takeaway

This problem shows the core converging-pointer invariant: on sorted data, one comparison eliminates one element. Comparing against the extreme partner is decisive. Too small means the left element cannot reach the target; too large means the right one cannot. When a problem gives you sorted input and asks about pairs (K-sum pairs, the inner loop of 3Sum, container problems), check for this one-comparison-one-elimination structure before reaching for hashing or search.