12 · Two Sum II — Input Array Is Sorted

In an Xcode test target:

import Testing

struct TwoSumSortedTests {

    @Test(arguments: [
        ([2, 3, 5, 8, 13], 16, [2, 5]),
        ([-3, -1, 0, 4], -4, [1, 2]),
        ([5, 5], 10, [1, 2]),
    ])
    func returnsTheOneBasedPositionsOfThePair(numbers: [Int], target: Int, expected: [Int]) {
        #expect(twoSum(numbers, target) == expected)
    }

    // MARK: - Privates
    private func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        []
    }
}

In a playground:

func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
    [] // your solution
}

let cases: [([Int], Int, [Int])] = [
    ([2, 3, 5, 8, 13], 16, [2, 5]),
    ([-3, -1, 0, 4], -4, [1, 2]),
    ([5, 5], 10, [1, 2]),
]
for (numbers, target, expected) in cases {
    let got = twoSum(numbers, target)
    print(got == expected ? "PASS" : "FAIL", numbers, target, "→", got, "expected", expected)
}

Two pointers, from both ends inward. The cues are "sorted" and "constant extra memory". Sorted means that moving right always gives a bigger number and moving left a smaller one — so a sum that is too small has exactly one fix (move the left end up) and a sum that is too big has exactly one fix (move the right end down). No lookup table is needed, because the order itself tells you which way to go.

Start with one finger on the smallest number and one on the largest. Add them. If the sum is the target, you are done. If it is too small, the smallest number can't be part of the answer — even paired with the largest, it falls short — so move the left finger right. If it is too big, the largest can't be part of it, so move the right finger left. Each step rules out one number for good.

Time O(n): every step moves one finger inward, and they can only meet once. Space O(1): two positions and a sum.

func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
    var left = 0
    var right = numbers.count - 1

    while left < right {
        let (sum, overflowed) = numbers[left].addingReportingOverflow(numbers[right])
        if !overflowed && sum == target {
            return [left + 1, right + 1]          // positions are 1-based
        }
        // On overflow the true sum is past Int's range in the direction of the larger value.
        let tooBig = overflowed ? numbers[right] > 0 : sum > target
        if tooBig { right -= 1 } else { left += 1 }
    }
    return []
}

Within the stated constraints the plain let sum = numbers[left] + numbers[right] is fine — say so, and say why you'd guard it in production (see the trap).

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above plus seven more — the minimum two entries, zeros, a long run of equal values before the partner, a mixed-sign array, and three arrays holding Int.max or Int.min, which crash the unguarded version — and 3,000 random sorted arrays checked against a brute-force search over every pair.

[2, 3, 5, 8, 13], target 16

[5, 5], target 10 — left on position 1, right on position 2, sum 10, answer [1, 2]. The two fingers start on different entries, so equal values are never a problem.

The sum of two valid entries can crash. The answer pair always fits in Int — its sum is the target — but the pairs you try on the way don't have to. With [1, 2, Int.max] and target 3, the first step adds 1 + Int.max, and Swift traps where C would wrap. Rewriting the check as numbers[left] > target - numbers[right] only moves the problem to the subtraction. addingReportingOverflow gives you the wrapped result plus a flag, and in a sorted array the direction of an overflow tells you which finger to move: overflowing upward means the sum is too big.

The other slip here is not Swift's fault: the answer is 1-based. Returning [left, right] passes every self-made test and fails the grader. Read the statement back (the R in REACTO) and you catch it.

• "Why does moving the left pointer never skip the answer?" → If the sum is too small with the largest remaining number, the current left number can't reach the target with anything, so discarding it is safe. Same argument mirrored for the right.
• "Return every pair, not just one." → On a match, record it, move both fingers, and skip past repeats of each value so pairs aren't duplicated. That skip is the heart of the next problem.
• "The array isn't sorted." → Either sort pairs of (value, position) — O(n log n), O(n) space — or use the dictionary from problem 3, O(n) and O(n). Sorting in place and returning positions doesn't work: the positions move.