Two Sum II – Input Array Is Sorted (LeetCode 167)

The problem

You get an array numbers sorted in non-decreasing order and a target. Exactly one pair adds up to the target. Return the two positions as 1-indexed [i, j] with i < j. You must use only constant extra space.

Input:  numbers = [1, 3, 4, 5, 7, 11], target = 9
Output: [3, 4]

4 + 5 = 9, and they sit at 1-indexed positions 3 and 4.

How to think about it

Start with brute force. Try every pair with two nested loops: O(n²). The classic Two Sum trick, a hash map of complements, gets O(n) time but uses O(n) space, which this version forbids.

The key insight: sorting tells you which way to move. Put i at the smallest number and j at the largest, and look at their sum. If it’s too small, the only way to increase it is to move i right, since moving j left would only make it smaller. If it’s too big, move j left. Each comparison throws away one candidate for good.

Why you can’t skip the answer. Suppose the sum is too small. Then numbers[i] paired with any j' ≤ j is also too small, because numbers[j'] is at most numbers[j]. So numbers[i] can’t be part of the answer, and dropping it is safe. The same argument works in reverse for j. That’s the proof interviewers like to hear.

Which pattern is this? Converging two pointers. The tell is “sorted array, find a pair with a sum (or difference) condition”.

Approach

1. Set i = 0 and j = n - 1.
2. While i < j, compute s = numbers[i] + numbers[j].
3. If s == target, return [i + 1, j + 1].
4. If s < target, move i right; otherwise move j left.
5. If the pointers meet, there’s no pair (not possible under the problem’s guarantee).

Solution

def two_sum_sorted(nums, target):
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target: return [i+1, j+1]   # 1-indexed answer
        if s < target: i += 1               # need bigger: drop the smallest
        else: j -= 1                        # need smaller: drop the largest
    return []
# two_sum_sorted([2,7,11,15], 9) -> [1,2]

Dry run

On numbers = [1, 3, 4, 5, 7, 11], target = 9:

The function returns [3, 4].

Complexity

• Time: O(n). Every step moves one pointer inward, so there are at most n − 1 steps.
• Space: O(1). Two indices and a sum.

Edge cases and pitfalls

• 1-indexed output. Returning [i, j] instead of [i+1, j+1] is the most common bug.
• Duplicates like [3, 3] with target 6 work fine: i = 0, j = 1.
• Negative numbers don’t change anything; the sort order is all that matters.
• Using the same element twice is prevented by i < j.
• Reaching for a hash map solves it but ignores the sorted input and breaks the O(1) space requirement.

Related problems

• Two Sum (LeetCode 1): the unsorted version, where a hash map of complements is the right tool.
• 3Sum (LeetCode 15): fix one number, then run exactly this two-pointer scan on the rest.
• Container With Most Water (LeetCode 11): another “move the pointer that can’t be part of a better answer” argument.