Module 04 · Two Pointers and In-Place Read/Write State

035. Two Sum in Sorted Array

Bridge · Download this solution · All solutions and shared helpers

Problem

Given a nondecreasing integer list, return one-based indices of two distinct positions summing to target, or [] if none exists. Return the first matching pair found by an inward scan starting at the endpoints. Leave the input unchanged.

Examples

Example 1

two_sum_sorted([2, 7, 11, 15], 9)
=> [1, 2]

The answer uses one-based indices.

Example 2

two_sum_sorted([3], 6)
=> []

A single cell cannot be used twice.

Example 3

two_sum_sorted([-2, 0, 2, 3], 1)
=> [1, 4]

Negative values do not invalidate sorted-order reasoning.

Reveal the worked solution and reasoning

Why this mechanism works

Sorted order makes a too-small sum informative: with the same left endpoint, every smaller right endpoint gives an even smaller sum. Discard left. A too-large sum similarly rules out the current right endpoint. No hash map is needed because ordering provides the exclusion proof.

State and boundaries

left and right are inclusive candidate endpoints, with left<right. Any still-possible pair lies inside this region.

Protocol

Evaluate the endpoint sum.
Return indices plus one on equality.
Advance left if the sum is small.
Retreat right if it is large.
Return [] when fewer than two candidates remain.

Visualization

2 ........ 15 -> sum 17 > 9
2 ..... 11    -> sum 13 > 9
2 .. 7        -> sum  9

Python implementation

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

two_sum_sorted([2, 7, 11, 15], 9)

L2 two_sum_sorted: left, right = 0, len(nums) - 1
nums=[2, 7, 11, 15]; target=9; left=0; right=3

L4 two_sum_sorted: total = nums[left] + nums[right]
nums=[2, 7, 11, 15]; target=9; left=0; right=3; total=17

L10 two_sum_sorted: right -= 1
nums=[2, 7, 11, 15]; target=9; left=0; right=2; total=17

L4 two_sum_sorted: total = nums[left] + nums[right]
nums=[2, 7, 11, 15]; target=9; left=0; right=2; total=13

L10 two_sum_sorted: right -= 1
nums=[2, 7, 11, 15]; target=9; left=0; right=1; total=13

L4 two_sum_sorted: total = nums[left] + nums[right]
nums=[2, 7, 11, 15]; target=9; left=0; right=1; total=9

Result: [1, 2]. The answer uses one-based indices.

two_sum_sorted([3], 6)

L2 two_sum_sorted: left, right = 0, len(nums) - 1
nums=[3]; target=6; left=0; right=0

Result: []. A single cell cannot be used twice.

Why the solution is correct

Each movement removes only a frontier that cannot participate in a target-sum pair among the remaining values. Equality supplies two distinct valid positions. If the pointers meet, every possible pair has been ruled out.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Returning zero-based indices violates this kata's explicit convention. Moving the larger-valued endpoint on a too-small sum moves in the wrong direction.

Reasoning card

State: left and right are inclusive candidate endpoints, with left<right. Any still-possible pair lies inside this region.

Invariant: All discarded pairs cannot equal target.

Decision to rehearse: Move left when sum is too small and right when too large.

Finish: Return [] when fewer than two candidates remain

Transfer exercise

Count all pairs when duplicates exist; explain why one match may represent a product of two run lengths.