Two Sum II - Input Array Is Sorted Solution

Problem

Given a sorted array of integers, find two numbers that add up to a target value and return their positions. The array is 1-indexed in the output, meaning the first element is at position 1, not 0. There is guaranteed to be exactly one valid answer.

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

Counter-example: numbers = [1, 3, 5, 7], target = 9 → [2, 4] (3 + 7), not [3, 4] (5 + 7 = 12, too large).

Intuition

The sorted order is the key: if we place one pointer at the smallest value and another at the largest, their sum either hits the target or tells us which direction to move. A sum that's too small means we need a larger left value; a sum that's too large means we need a smaller right value. Each step eliminates one element with certainty, giving us O(n) total.

Approach 1 — Brute Force

Try every pair of indices and check whether they sum to the target.

Iterate left from index 0 to n - 2.
For each left, iterate right from left + 1 to n - 1.
If numbers[left] + numbers[right] == target, return [left + 1, right + 1].

1def twoSum(numbers: list[int], target: int) -> list[int]:
2    for left in range(len(numbers)):
3        for right in range(left + 1, len(numbers)):
4            if numbers[left] + numbers[right] == target:
5                return [left + 1, right + 1]  # convert to 1-indexed output
6    return []

Time: O(n²) — every pair is checked in the worst case.
Space: O(1) — no extra data structures.

Approach 2 — Two Pointers

Use the sorted property to converge from both ends in a single pass.

Place left at index 0 and right at index n - 1.
Compute current_sum = numbers[left] + numbers[right].
If current_sum == target, return [left + 1, right + 1].
If current_sum < target, increment left — we need a larger value on the left.
If current_sum > target, decrement right — we need a smaller value on the right.
Repeat until a solution is found.

1def twoSum(numbers: list[int], target: int) -> list[int]:
2    left, right = 0, len(numbers) - 1
3    while left < right:
4        current_sum = numbers[left] + numbers[right]
5        if current_sum == target:
6            return [left + 1, right + 1]  # convert to 1-indexed output
7        elif current_sum < target:
8            left += 1   # sum too small — move toward larger values
9        else:
10            right -= 1  # sum too large — move toward smaller values
11    return []

Time: O(n) — each pointer moves at most n steps total, so the while loop runs at most n iterations.
Space: O(1) — only two index variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only for tiny inputs or interviews where you need to state the naive solution first
Two Pointers	O(n)	O(1)	Always when the array is sorted — this is the intended solution

Common Mistakes

Returning 0-indexed results — the problem explicitly asks for 1-indexed output, so both return values need + 1. The two-pointer logic itself stays 0-indexed throughout.
Moving the wrong pointer — when current_sum < target you must move left right (not right left), and vice versa. Moving the wrong pointer skips valid pairs.
Using a hash map from Two Sum I — a hash map works but uses O(n) space, violating the constant-space constraint. The sorted property makes O(1) space possible, which is the whole point of this variant.
Using <= in the while condition — left < right is correct; allowing left == right would let you pair an element with itself, which is not a valid answer.
Assuming the array is 0-indexed — numbers[0] is the first element internally, but the output positions are 1-based. Confusing these produces off-by-one answers like [0, 1] instead of [1, 2].

Two Sum II - Input Array Is Sorted — Solution