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 extra rules distinguish this from plain Two Sum: the input is already sorted, and your solution must use O(1) extra space — so the usual hash map is off the table.

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; negatives change nothing about 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

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 []

Complexity: O(n^2) time, O(1) space. At n = 3 * 10^4 that’s ~4.5 * 10^8 pair checks — over the limit, and it ignores the sortedness 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 — the classic halving search that compares the middle element and discards the half that can’t contain the key.

from typing import List

class Solution:
    def twoSum(self, 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 → 3 < 4 → lo = 2; mid = 2 → 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 full 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 proves numbers[left] dead — it was just paired with the largest value still in play, and every future partner is smaller — so left advances. Symmetrically a too-large sum kills numbers[right]. Every comparison permanently eliminates one element, so at most n - 1 steps reach the unique answer. No memory, no search.

from typing import List

class Solution:
    def twoSum(self, 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; forgetting the + 1 on both positions is the classic slip.
• Moving the wrong pointer: the discard argument only works one way — a small sum indicts left, a large sum indicts right. Swapping them breaks correctness, not just speed.
• Reaching for the hash map: it works but uses O(n) space, violating the stated constraint — mention it, then set it aside.
• Binary searching the whole array instead of i+1..n-1: you may find i itself when need == numbers[i], illegally reusing one element.

Pattern takeaway

This problem is the cleanest statement of the converging-pointer invariant: sorted data lets one comparison eliminate one element forever. The sum against the extreme partner is a certificate — too small means the left element has no hope, too large means the right one doesn’t. Any time a problem hands you sorted input and asks about pairs (K-sum pairs, 3Sum’s inner loop, container problems), look for that same one-comparison-one-elimination certificate before reaching for hashing or search.