Two Sum II - Input Array Is Sorted

Learning goal: Recognize what the sorted-input version of Two Sum asks you to return.

Core idea We need two different entries whose values add to target. The answer is not the values themselves: it is their one-based positions. Unlike ordinary Two Sum, the array is already sorted, which gives us useful information about how sums change when a pointer moves.

What to return

For numbers = [2, 3, 4, 8, 11, 15] and target = 15, the pair is 4 + 11. Their zero-based positions are 2 and 4, so the required answer is [3, 5].

Micro-example

• Start with the smallest and largest values: 2 + 15 = 17.
• Because the sum is too large, the useful next move will be toward a smaller right value.

Pitfalls

• Returning zero-based indices instead of one-based indices
• Reusing the same element twice
• Forgetting that the input is sorted and treating it like an arbitrary array

Recap

• Find exactly one pair summing to target.
• Return one-based indices.
• Sorted order is the key extra structure.

Learning goal: Understand why two pointers can eliminate impossible pairs safely.

Core idea Place left at the first element and right at the last element. Their values form the widest possible pair. If the sum is too large, keeping left and moving right farther right is impossible because right is already at the maximum position; moving right left is the only direction that can reduce the sum. If the sum is too small, moving left right is the only direction that can increase it.

Pointer decisions

Micro-example For [2, 3, 4, 8, 11, 15] and target 15, 2 + 15 = 17, so move right. The new candidate 2 + 11 = 13 is now too small, so move left.

Pitfalls

• Moving the wrong pointer reverses the intended sum adjustment.
• Checking only adjacent values misses the purpose of the endpoints.
• The proof depends on sorted order; it is not valid for an arbitrary array.

Recap

• right moves left to reduce a sum.
• left moves right to increase a sum.
• Every move safely removes impossible pairs.

Learning goal: Turn the steering rule into a one-pass algorithm.

Core idea The algorithm maintains a candidate interval from left through right. At each iteration, it examines only the two endpoint values. Since each move advances one pointer inward, no index is revisited in the opposite direction, giving linear time and constant auxiliary space.

Algorithm plan

1. Set left = 0 and right = numbers.length - 1.
2. While left < right, compute sum = numbers[left] + numbers[right].
3. If sum equals target, return [left + 1, right + 1].
4. If sum is too large, decrement right.
5. Otherwise, increment left.

while left < right:
    total = numbers[left] + numbers[right]
    if total == target:
        return [left + 1, right + 1]
    if total > target:
        right -= 1
    else:
        left += 1

Micro-example At left = 0, right = 5, the sum is 17, so index 5 cannot pair with index 0 or any later left index to make 15. Move right inward.

Pitfalls

• Use left < right, not left <= right, because the indices must differ.
• Add 1 to both indices in the returned answer.
• Do not allocate a map or a second array.

Recap

• Two endpoint pointers are sufficient.
• Each iteration makes one decisive inward move.
• The loop is a single pass with O(1) extra space.

Learning goal: Trace every pointer decision on a concrete input.

Core idea Use numbers = [2, 3, 4, 8, 11, 15] and target = 15. The pointers begin at indices 0 and 5. We repeatedly compare the endpoint sum with the target and move exactly one pointer inward. The active interval shrinks without losing the answer.

Trace

Micro-example The first sum, 17, is too high, so 15 cannot be part of a valid pair with any value at or after 2. After three pointer moves, 4 + 11 reaches the target.

Pitfalls

• Do not move both pointers after a non-matching sum; only one direction is justified.
• Keep the trace indices zero-based internally.
• Translate to one-based indices only when returning.

Recap

• The sequence of sums is 17, 13, 14, 15.
• The final zero-based pair is (2, 4).
• The required one-based answer is [3, 5].

Learning goal: Avoid the most common incorrect implementations of Two Sum II.

Core idea The two-pointer method is short, but its correctness relies on specific assumptions. The input must be sorted, the pointers must move in the direction dictated by the comparison, and the answer must use one-based indexing. These details distinguish the intended solution from a superficially similar search.

The hash-map mistake

A hash map solves ordinary Two Sum in O(n) time, but it uses O(n) extra space and ignores the sorted structure. Reusing it is correct in terms of the answer, yet it misses the central opportunity of this problem: the sorted array lets us solve the task with O(1) extra memory.

Micro-example If sum > target, moving left right cannot help: every later left value is at least as large. Move right left instead.

Pitfalls

• Applying two pointers to an unsorted array without sorting first
• Moving both pointers after every comparison
• Returning [left, right] instead of [left + 1, right + 1]
• Letting pointers cross or reuse one element

Recap

• Hash maps work but waste the sorted-input advantage.
• Direction follows whether the current sum is high or low.
• Validate indexing and pointer boundaries carefully.

Learning goal: Prove the efficiency of the two-pointer solution and summarize when to use it.

Core idea Each iteration moves either left one position right or right one position left. Neither pointer ever reverses direction, so together they make at most n - 1 inward moves before meeting. The algorithm therefore examines a linear number of candidates and stores only a few variables.

Complexity

Micro-example For six values, the walkthrough made only three pointer moves before finding the answer. Even in the worst case, the pointers can cross after only a linear number of moves.

Pitfalls

• Do not count the input array as extra space.
• Do not claim O(log n) merely because the array is sorted; this algorithm scans inward.
• Sorting would change the problem's given order and is unnecessary here.

Recap

• Sorted input enables safe pointer steering.
• The final bounds are O(n) time and O(1) extra space.
• Prefer this structure-aware method over a familiar hash map.