Two Sum II

You'll use sorted order to rule out many pairs at once, with two pointers that start at the ends. You need indexes and sorted lists. Read Two Sum first. Related chapter: two pointers.

1. The problem

You get a list of integers sorted from smallest to largest, and a target. Find two different positions whose values sum to the target. Return their one-based indexes, smaller first, using only a fixed amount of extra space. This is Two Sum II (LC 167).

LeetCode promises exactly one answer. Our function also returns [] when there is none, including for an empty list. It doesn't change the input. "Sorted" and "fixed extra space" are the phrases that matter: they rule out the hash map from Two Sum and point to something else.

2. A correct baseline

Try every pair of positions. Add 1 to each index when returning, because Python counts from zero.

def baseline(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

assert baseline([1, 2, 4, 6, 9], 8) == [2, 4]
assert baseline([3, 3], 6) == [1, 2]
assert baseline([-3, 0, 4], 1) == [1, 3]
assert baseline([], 8) == []

This takes O(n²) time in the worst case: the work grows with the square of the list's length. With 10,000 numbers, that's about fifty million pairs. A hash map would take O(n) time, but it needs O(n) extra space, which the problem doesn't allow.

The bottleneck. The brute force tests partners one at a time, even when sorted order already rules out a whole group of them.

3. The observation

Take [1, 2, 4, 6, 9] with target 8. Add the smallest and the largest: 1 + 9 = 10, too big. Could 9 work with anything else? Every other partner is at least 1, so every sum with 9 is at least 10. So 9 is out.

In general, compare the smallest and largest values left. If their sum is too big, the largest value can't work with any partner: even the smallest was too much. Drop it. If the sum is too small, the smallest value can't work with any partner: even the largest wasn't enough. Drop that one.

This works because the list is sorted. Sorted order is what makes it safe to drop a value after one comparison.

4. The solution and a trace

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        """For sorted input, return one-based matching indexes or []."""
        left = 0
        right = len(numbers) - 1
        # Any pair not ruled out lies between these two indexes.
        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 []

solve = Solution().twoSum
assert solve([1, 2, 4, 6, 9], 8) == [2, 4]
assert solve([3, 3], 6) == [1, 2]
assert solve([-3, 0, 4], 1) == [1, 3]
assert solve([], 8) == []

Trace [1, 2, 4, 6, 9], target 8:

Try [3, 3] with target 6: the first comparison, 3 and 3, already matches. left < right keeps the two positions different.

5. Why it works

What stays true. Every pair that could still be the answer lies between left and right. That's true at the start, when the pointers are at the ends. Each move drops only a value that can't be in any remaining answer, so it stays true.

A returned pair is right. It sums to the target, and left < right means the positions differ.

It never misses the answer. If an answer exists, it's always between the pointers, so the loop reaches it before they meet. When they meet with no match, there's no pair left to find.

6. Cost, edge cases, and failure

Cost. Each step moves one pointer inward, so there are at most n − 1 comparisons. That's O(n) time, growing in step with the list, and O(1) extra space.

Edge cases. Duplicates and negative numbers keep the list sorted, so they need no special handling. Remember to add 1 to each pointer before returning.

Where it fails. On an unsorted list, dropping a value isn't safe. Here a valid pair exists, but the pointers miss it:

assert baseline([3, 2, 4], 6) == [2, 3]
assert solve([3, 2, 4], 6) == []  # Deliberately violates the sorted-input precondition.

Sorting the list first would lose the original indexes unless you track them. For unsorted input, use the hash map from Two Sum instead.

import random
rng = random.Random(167)
for _ in range(1500):
    numbers = sorted(rng.randint(-10, 10) for _ in range(rng.randrange(16)))
    target = rng.randint(-20, 20)
    before = numbers.copy()
    actual, expected = solve(numbers, target), baseline(numbers, target)
    assert bool(actual) == bool(expected)
    if actual:  # Several answers are allowed in generated tests.
        i, j = actual
        assert 1 <= i < j <= len(numbers)
        assert numbers[i - 1] + numbers[j - 1] == target
    assert numbers == before