Two Sum on a Sorted Array: The Two Pointers Opener

"Two Sum II" is a Medium-level staple in Amazon, Meta, Apple loops, and it is a textbook fit for the Two Pointers pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 1 of 12 in the Two Pointers arc.

The Problem

Given a 1-indexed array of integers numbers sorted in non-decreasing order, find two numbers that add up to a specific target and return their indices. Exactly one solution exists, and you may not use the same element twice. The twist that separates this from classic Two Sum: you must use only constant extra space.

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Because numbers[1] + numbers[2] = 2 + 7 = 9.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

The word sorted is the giveaway. A hash map solves unsorted Two Sum in O(n) time but O(n) space; sorted input lets converging pointers exploit order instead of memory, which is exactly the trade interviewers want you to articulate.

The Approach

Place left at the start and right at the end. Their sum is either the answer, too small, or too big. Too small means nothing pairs with numbers[left] — every remaining candidate to its right only shrinks the pool — so advance left. Too big means numbers[right] can never work, so retreat right.

Each step permanently eliminates one element from consideration, so the loop terminates in at most n − 1 steps with the guaranteed pair.

Python Solution

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """Return 1-based indices of the pair summing to target."""
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left + 1, right + 1]
        if current < target:
            left += 1   # left value too small to ever pair up
        else:
            right -= 1  # right value too large for any partner
    return []  # unreachable per problem statement

Complexity

• Time: O(n) — each iteration discards one candidate, so at most n − 1 iterations
• Space: O(1) — two integer indices regardless of input size

Interview Tips and Follow-Ups

• Asked the unsorted version? That is classic Two Sum — hash map, O(n) time, O(n) space. Say the trade-off out loud.
• Follow-up favorite: return all unique pairs. Sort, then converge, skipping duplicates on both sides after each hit.
• State the invariant (everything left of left and right of right is eliminated) — interviewers probe whether the pointer moves are justified, not memorized.

That wraps part 1 of the Two Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.