Two Sum II: Converging Two Pointers on a Sorted Array

LeetCode Two Sum II - Input Array Is Sorted (problem 167) is one of the cleanest examples of the converging two-pointer technique. The sorted input is the key constraint, and it changes the optimal strategy entirely compared to the original Two Sum. No hash map needed. No extra space at all.

The problem

You are given a 1-indexed array of integers numbers that is already sorted in non-decreasing order. Find two numbers that add up to a specific target number. Return their indices as a 1-indexed array [index1, index2] where index1 < index2.

Exactly one solution exists. You cannot use the same element twice. The solution must use only constant extra space.

Examples:

• numbers = [2, 7, 11, 15], target = 9 returns [1, 2] because 2 + 7 = 9.
• numbers = [2, 3, 4], target = 6 returns [1, 3] because 2 + 4 = 6.
• numbers = [-1, 0], target = -1 returns [1, 2] because -1 + 0 = -1.

The sorted order is what makes this problem different from the original Two Sum. With a sorted array, you can exploit the ordering to find the answer without any auxiliary data structure.

Why not use a hash map?

You could solve this with the same hash map approach from Two Sum. That gives O(n) time but O(n) space. The problem explicitly requires O(1) extra space. A hash map violates that constraint.

You could also try binary search: for each element, binary search for its complement. That gives O(n log n) time and O(1) space. It works, but there is a simpler O(n) approach that takes full advantage of the sorted order.

The approach: converging two pointers

Place one pointer at the start of the array (left) and one at the end (right). Compute the sum of the two values.

• If the sum equals the target, return the 1-indexed positions.
• If the sum is too small, move left one step to the right. The array is sorted, so moving left forward increases the sum.
• If the sum is too large, move right one step to the left. Moving right backward decreases the sum.

Each step eliminates at least one candidate. The pointers converge toward the middle and will meet at the answer. Since the problem guarantees exactly one solution, the pointers will always find it before they cross.

Visual walkthrough

Let's trace through numbers = [2, 7, 11, 15] with target = 9. The orange pointer is left and the green pointer is right. Indices shown are 1-indexed.

Notice how the search space shrinks with every step. When the sum is too large, moving right inward guarantees a smaller sum on the next check. When the sum is too small, moving left forward guarantees a larger one. There is never a reason to backtrack.

The code

Here is the complete Python solution:

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1

The code works with 0-indexed pointers internally and converts to 1-indexed on return. The while left < right loop guarantees that two distinct elements are always being considered. Since exactly one solution exists, the function always returns inside the loop.

Why convergence works

The correctness of this algorithm relies on a simple invariant: the answer always lies within the range [left, right].

At the start, left = 0 and right = n - 1, so the entire array is in range. Now consider what happens when the sum is too small. The current sum is numbers[left] + numbers[right]. Since numbers[right] is the largest remaining value, no other value paired with numbers[left] can produce a larger sum. That means numbers[left] cannot be part of the answer. Moving left forward is safe because it only discards a value that was already ruled out.

The same logic applies in reverse when the sum is too large. numbers[left] is the smallest remaining value, so no other value paired with numbers[right] can produce a smaller sum. numbers[right] is not part of the answer. Moving right backward is safe.

Each step discards exactly one element that provably cannot be in the solution. The range shrinks by one each iteration, and the answer remains inside.

Complexity analysis

Time: O(n). Each step moves one pointer inward. The two pointers start a total of n - 1 positions apart and each step closes that gap by one. At most n - 1 steps.

Space: O(1). Only two integer variables (left and right) are used. No hash map, no auxiliary array, no recursion stack.

The two-pointer approach wins on space while matching the hash map on time. When the input is already sorted, this is the optimal strategy.

The building blocks

This problem is built from one fundamental building block.

Converging two pointers on sorted input

Start two pointers at opposite ends of a sorted array. Adjust them based on how the current result compares to the target. If the combined value is too small, advance the left pointer. If too large, retreat the right pointer.

This same pattern drives the inner loop of several harder problems:

• 3Sum: fix one element, then use converging pointers to find the remaining pair
• Container With Most Water: converge from both ends, moving the shorter side inward
• Trapping Rain Water: process the smaller boundary first using converging pointers
• 3Sum Closest: same convergence, but track the closest sum instead of an exact match

If you can write Two Sum II from memory, the two-pointer inner loop of all these problems is already handled. The harder problems just add an outer loop or a different objective on top of the same convergence step.

Edge cases to watch for

A few scenarios to keep in mind:

• Answer at the extremes. numbers = [1, 2], target = 3. The pointers start on the answer immediately. The first check finds it. Your code should not skip the initial position.
• Target requires middle elements. numbers = [1, 2, 3, 4, 5], target = 5. The answer is [1, 4] (values 2 and 3). The pointers must converge inward past the endpoints to reach it.
• Negative numbers. numbers = [-3, -1, 0, 2, 5], target = 1. The sum logic works identically with negative values. numbers[-3] + numbers[5] = -3 + 5 = 2, too large, so move right. numbers[-3] + numbers[2] = -3 + 2 = -1, too small, so move left. The convergence does not care about sign.

From understanding to recall

Two Sum II is a problem that feels obvious once you see it. "Two pointers, move them inward, done." But reconstructing it from scratch in an interview means remembering the details: which pointer moves when, how the 1-indexed return works, why left < right is the right loop condition.

These small details fade after a week. The fix is not to re-read the solution. It is to practice typing it from memory at spaced intervals. After a few repetitions, the convergence pattern becomes automatic. You stop thinking about Two Sum II as a problem to solve and start thinking of it as a brick you already own.

Related posts

• Two Sum - The original problem using hash map complement lookup instead of two pointers
• 3Sum - Uses converging two pointers as its inner loop after fixing one element

---

Visual Learner? See how sorting algorithms work with our Quick Sort Visualization -- sorting is the prerequisite that makes the two-pointer technique possible.