Two Sum II

Brute force — ignore the sorting

Every pair, same as unsorted Two Sum:

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    n = len(numbers)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

O(n²) time — and it never once used the fact that the input is sorted. When a problem hands you structure and your solution doesn't touch it, that's the smell to chase.

(A hash map also still works in O(n) time / O(n) space — but the follow-up asks us to do better on space.)

Converging pointers — spend the sorting

Put left on the smallest element, right on the largest, and reason about the sum:

• sum == target → done.
• sum > target → the current numbers[right] is too big for every remaining partner (they're all ≥ numbers[left]), so it can never be in the answer: right -= 1.
• sum < target → symmetric: numbers[left] is too small for every remaining partner: left += 1.

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        if s > target:
            right -= 1
        else:
            left += 1
    return []

Each step permanently retires one element with a proof it can't participate. n elements, so at most n steps: O(n) time, O(1) space.

The takeaway to keep: sorted order is a resource. Here it replaced an entire hash map — the pointers extract the same "have I seen your partner?" information from position instead of memory.