Two pointers: shrink one search space | DSA & Design, Connected

Picture

In a sorted row [1,2,4,7], seek a pair totaling 9. Checking every pair repeats work.

Predict

When the sum is too small, which pointer can safely move?

Walk through the small example

Left pointer. An ordered comparison lets one pointer move while ruling out every pair it skips.

Mental model and complete Python solution

Picture a rectangle of candidate pairs. Comparing the two ends eliminates one complete edge of that rectangle. The invariant is that any valid pair still lies between the pointers.

What the function promises: Return one pair of zero-based positions in a nondecreasing list, or None. Distinct positions are required.

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

assert two_sum_sorted([1, 2, 4, 7], 9) == (1, 3)
assert two_sum_sorted([1, 2, 4, 7], 20) is None

Work and storage: O(n) time and O(1) extra space.

When to recognize it: An ordered comparison lets one pointer move while ruling out every pair it skips.

Check before applying it: Without sorted order, the same pointer move is not justified; use a lookup map or sort while preserving needed identities.

Change one rule

The list is unsorted and original indices must be returned.

See what changes

Use a dictionary of previously seen complements, or sort value-index pairs and retain their original positions.

Connect

invariants: Each move must preserve every still-possible pair.

dictionaries: An unsorted two-sum question often favors a complement map.