Two Sum II: Pair Sum in a Sorted Array

This is the canonical two-pointer problem: the converging template with almost nothing added. Interviewers use it as a warm-up, and they use it to check one thing — whether you notice that the array is sorted and use that fact. A candidate who writes a hash map here gets a working answer and a follow-up question: "can you do it without the extra memory?"

The problem

You are given a list of integers sorted in ascending order and a target value. Exactly one pair of different positions holds two values that add up to the target. Return the two positions, counting from 1, smaller position first.

• numbers = [1, 3, 4, 6, 8, 11], target = 10 → [3, 4], because numbers[2] + numbers[3] = 4 + 6 = 10, and positions count from 1.
• numbers = [-3, -1, 0, 2, 5], target = -4 → [1, 2], because -3 + -1 = -4.

Constraints: 2 ≤ len(numbers) ≤ 10⁵; values between -10⁹ and 10⁹; exactly one valid answer; the same position may not be used twice. Use only O(1) extra space.

Clarifying questions

• Can values repeat? Yes. [2, 2, 3] with target 4 has answer [1, 2] — two positions with the same value is fine.
• 1-based or 0-based positions? 1-based here. Confirm it; it is the most common silly error.
• What if there is no pair? Guaranteed not to happen, but returning [] costs nothing and makes the function safe.
• Can I modify the input? Not needed; we only read it.

Approach 1: the simple way

Try every pair of positions i < j and return the first that adds up.

1def pair_sum_brute(numbers: list[int], target: int) -> list[int]:2    """Try every pair. Returns 1-based positions."""3    n = len(numbers)4    for i in range(n):5        for j in range(i + 1, n):6            if numbers[i] + numbers[j] == target:7                return [i + 1, j + 1]8    return []

Time O(n²), space O(1). At n = 10⁵ that is up to about 5 × 10⁹ pairs — around 50 seconds even at 10⁸ steps per second, and several minutes in Python. The constraint rules it out.

Notice what the brute force ignores: the sorting. Whenever a solution ignores a property the problem went out of its way to give you, there is a better solution.

A middle step is worth mentioning aloud: for each value, binary search for target - value to its right. That is O(n log n) time and O(1) space — fast enough, but it still ignores what each failed search tells you. A hash map of value to position gives O(n) time but O(n) space, which the problem forbids.

The key insight

Look at the smallest and the largest values together. Their sum is either right, too big or too small.

If it is too big, the largest value cannot be in the answer. Its smallest possible partner is the smallest value, and that pair already overshoots; any other partner is at least as large, so it overshoots too. Throw the largest value away.

If it is too small, the smallest value cannot be in the answer. Its largest possible partner already falls short. Throw the smallest value away.

Either way one comparison removes one value and every pair it could form, while the answer stays inside the remaining range. That is why only n − 1 comparisons are needed at most, and why a single pass beats both binary search and the pair table.

Why the answer can never be skipped. Say the answer uses positions a and b, with a < b. The pointers start outside or on them: left ≤ a and right ≥ b. For left to step past a, the sum numbers[a] + numbers[right] would have to be too small. But right ≥ b, so numbers[right] ≥ numbers[b], and the sum is at least the target — never too small. The same argument stops right from stepping past b. So the pointers must land on a and b together, and the loop returns them.

Here are the three approaches side by side. In an interview, naming all three in one breath — and saying why you pick the last — is a strong opening.

Approach 2: converging pointers

1. Put left on the first position and right on the last.
2. Add the two values.
3. Equal to the target: return both positions, plus one each.
4. Smaller than the target: left += 1. Larger: right -= 1.
5. Repeat while left < right.

1def pair_sum_sorted(numbers: list[int], target: int) -> list[int]:2    """Return the 1-based positions of the two values that add up to target."""3    left, right = 0, len(numbers) - 14    while left < right:5        current = numbers[left] + numbers[right]6        if current == target:7            return [left + 1, right + 1]     # the problem counts from 18        if current < target:9            left += 1                        # numbers[left] is too small for anyone10        else:11            right -= 1                       # numbers[right] is too big for anyone12    return []

Dry run on [1, 3, 4, 6, 8, 11], target 10:

Five comparisons, where the brute force would check up to fifteen pairs. Each row removed one value for good: 11, then 1, then 8, then 3.

Complexity. Each round moves one pointer inward by one, and they start n − 1 apart, so there are at most n − 1 rounds of constant work: O(n) time. Two integer indices: O(1) space.

Edge cases

• Two elements. left = 0, right = 1; one comparison decides. Works.
• Repeated values. [2, 2, 3], target 4: 2 + 3 = 5 too big, right → 1; 2 + 2 = 4 → [1, 2]. Two different positions, same value — correct.
• Negative numbers. Nothing changes; the argument only needs sorted order. [-3, -1, 0, 2, 5], target −4 returns [1, 2].
• Large values. Sums reach 2 × 10⁹, past a 32-bit integer. Python is fine; in Java or C++ use a 64-bit type.

We checked the two-pointer version against the brute force on 300 random sorted arrays of up to 15 values, with and without a valid pair. Doing the same yourself — a slow, obviously correct version plus a loop of random inputs — takes five minutes and catches almost every pointer bug.

Follow-ups

• "The array is not sorted; return original positions." Use a hash map from value to position in one pass: O(n) time, O(n) space. Sorting would lose the positions.
• "Count all pairs that add up to the target." On a match with distinct values, count one and move both pointers. With runs of equal values, count the run lengths and multiply — or, if the two values are equal, use k × (k − 1) / 2 for a run of length k.
• "Find the pair whose sum is closest to the target." Same loop; track the best abs(sum - target) seen and never return early except on an exact match.