Two Sum II - Input Array Is Sorted

The sorted property guarantees that pointer movements have monotonic effects on the sum. This transforms a search problem into an $O(1)$ elimination problem.

Pattern Summary

This problem uses the [Two Pointers] pattern.

• Recognition: Finding a pair of elements that sum to a target in a sorted array.
• Core Invariant: If nums[left] + nums[right] < target, no element to the left of right can form a valid pair with left because the array is sorted. The left candidate is permanently dead.
• Transformation: Replace $O(n \log n)$ binary searches or $O(n)$ hash map space with an $O(1)$ amortized state space elimination.

$\rightarrow$ Read the full theoretical foundation: [Two Pointers]

Real-World Analogues

Financial Matching

Budget Allocation
Given a sorted list of component costs, find two components that exactly exhaust a budget. Searching with opposing pointers allows an embedded system to find the pair without allocating a hash table in constrained memory.

Interview Abstraction

LeetCode 167 asks: given a 1-indexed array of integers numbers sorted in non-decreasing order, return the indices of the two numbers that add up to target using only $O(1)$ extra space.

Why This Problem Matters

This problem bridges the gap between searching and structural invariants. It teaches you how a sorted property enables $O(1)$ search space reduction from two ends.

Recognition

Reach for this pattern when:

• ✓ The input is a sequence that is already sorted.
• ✓ You are looking for pairs that satisfy a mathematical relation (sum, difference, product).
• ✓ The problem explicitly restricts auxiliary space to $O(1)$.

The Mental Shift

Naive Thought   → "For each number, binary search the rest of the array for the complement."
Correct Thought → "The sorted order tells me exactly which pointer to move to adjust the sum."

If the sum is too small, you must increase it. Because the right pointer is already at the maximum possible remaining value, the only way to increase the sum is to increment the left pointer.

Solution Evolution

Why This Beats Binary Search

Binary search answers: “Where is the complement in the remaining array?”
The two-pointer approach answers: “Can we eliminate an entire row/column of the search space in $O(1)$?”

By moving one pointer, we implicitly eliminate all combinations involving that pointer, dropping the factor from $O(\log n)$ to amortized $O(1)$.

From Pattern → Code

The opposing pointers pattern maps to simple policies:

# 1. SUM: Compute current state safely
if target - numbers[left] > numbers[right]:
    # 2. INCREASE: Sum is too small
    left += 1
elif target - numbers[left] < numbers[right]:
    # 3. DECREASE: Sum is too large
    right -= 1
else:
    # 4. MATCH: Return 1-indexed positions
    return [left + 1, right + 1]

Optimal Solution

from typing import List

def two_sum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    out = []
    
    while left < right:
        # Safe comparison avoiding integer overflow
        if target - numbers[left] > numbers[right]:
            left += 1
        elif target - numbers[left] < numbers[right]:
            right -= 1
        else:
            out.append(left + 1)
            out.append(right + 1)
            return out
            
    return out

Visual Walkthrough

Tracing numbers = [2, 7, 11, 15], target = 9.

Complexity Analysis

Edge Cases

Common Mistakes

• ❌ Using Extra Space: Falling back to a Hash Map approach which violates the $O(1)$ auxiliary space constraint.
• ❌ Integer Overflow: In languages with bounded integers, computing numbers[left] + numbers[right] can overflow. The structure target - numbers[left] > numbers[right] guarantees safety.
• ❌ 0-Indexing: Forgetting that the problem explicitly requests 1-indexed output format.

Problem Progression

Mastering this problem enables you to solve a progression of harder variations:

1. 3Sum (Medium): Wrapping Two Sum II in an outer loop to find triplets.
2. 4Sum (Medium): Extending to quadruplets with early termination.
3. Container With Most Water (Medium): Modifying the pointer elimination logic for area instead of sum.

Principal Lens

If you remember one thing: A sorted array transforms pair finding from a $O(N)$ memory hashing task into an $O(1)$ memory search space reduction task. If the sum is too small, your only valid move is to advance the left pointer.