Solving Two Sum with Two Pointers: Reducing the Search Space

Today’s problem: LeetCode 167 - Two Sum II - Input array is sorted (Easy)

Given an array of integers sorted in ascending order, find two numbers such that they add up to a specific target number (you may not use the same element twice). Return the indices i and j of the two numbers, where i < j.

Assume that each input has exactly one solution.

Example:

• Input: numbers = [2, 7, 11, 15], target = 9
• Output: [0, 1]

(Note: this differs slightly from the original problem — indices here start from 0, which feels more natural.)

Two Sum is the very first problem on LeetCode, so you’ve probably seen it before. At first glance, Two Sum II seems just as straightforward as the original Two Sum. However, this problem actually has a hidden twist — once the constraint that the array is sorted is added, it calls for an entirely different approach.

If you jump straight to the answer, you’ll find it’s just a standard two-pointer solution. Two pointers, $O(n)$ time. But if you only look at the answer without understanding the reasoning behind it, you’ll find yourself in the frustrating cycle of “I get it when I read it, but I’m lost when I try it.”

In fact, what lies behind this two-pointer solution is the general idea of reducing the search space. In this article, I’ll walk you through the reasoning behind this approach in detail, so you can truly understand this classic problem. And next time you encounter a similar problem, you’ll be able to quickly come up with this kind of solution.

This article will cover:

• Correctness explanation of the two-pointer solution
• The underlying principle: reducing the search space
• Another example problem using the same principle
• Related problems

The Two-Pointer Solution

Before tackling Two Sum II, you probably already know how to solve Two Sum. Using a hash map with a single linear scan gives you an $O(n)$ time, $O(n)$ space solution. So in Two Sum II, can the sorted array constraint help us reduce the complexity?

Seeing the sorted condition, your first thought might be binary search. But think again — you’d need to fix one number and binary search for the other, giving $O(n \log n)$ time. That’s clearly not good enough. We can already achieve $O(n)$ time and $O(n)$ space without sorting. So our goal should be: $O(n)$ time, $O(1)$ space!

How can we achieve this? That’s where the two-pointer solution comes in. Let’s first look at what the answer looks like:

public int[] twoSum(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i < j) {
        int sum = nums[i] + nums[j];
        if (sum < target) {
            i++;
        } else if (sum > target) {
            j--;
        } else {
            return new int[]{i, j};
        }
    }
    return new int[]{-1, -1};
}

The logic is beautifully simple — it uses just two pointers, one moving only to the right, the other only to the left. In a single pass, we get the answer.

Many solutions just present this answer as if the reasoning is self-evident. But in reality, this approach isn’t immediately obvious. The first time I saw this solution, I called it the Amazing O(n) Solution. What makes it remarkable is that it compresses $O(n^2)$ complexity down to $O(n)$ while maintaining correctness. We need to explain why it’s guaranteed to find the solution without missing any cases.

Correctness of the Two-Pointer Solution

Consider the two numbers pointed to by our pointers: A[i] and A[j]. Since the array is sorted, at the start, A[i] is the smallest number and A[j] is the largest. We compare A[i] + A[j] with the target sum target, and there are two possible outcomes:

• A[i] + A[j] is too large. We need to find two smaller numbers. Since A[i] is already the smallest element, adding any number other than A[i] to A[j] would only make the sum larger. Therefore, A[j] cannot be part of a valid solution, so we move j one step to the left to eliminate A[j].
• A[i] + A[j] is too small. We need to find two larger numbers. Since A[j] is already the largest element, adding any number other than A[j] to A[i] would only make the sum smaller. Therefore, A[i] cannot be part of a valid solution, so we move i one step to the right to eliminate A[i].

After eliminating the leftmost or rightmost number in the first step, we look at the subarray A[i..j], where A[i] is again the smallest and A[j] is again the largest. We can continue this elimination process. By induction, after $n$ steps, we will have exhausted all possibilities.

As you can see, whether A[i] + A[j] is too large or too small, we can always eliminate one number. This elimination method is very similar to binary search. Binary search eliminates half the elements each time to reduce the number of comparisons; this method eliminates one element each time. And both take advantage of the sorted array property.

At this point, we’ve unveiled half of the mystery behind this solution. Next, let’s use a more intuitive approach to truly understand this problem from the perspective of the search space.

How the Search Space Shrinks

In this problem, we’re looking for a pair of indices $(i, j)$ that satisfy these constraints:

• $i$ and $j$ are both valid indices, i.e., $0 \le i < n, 0 \le j < n$
• $i < j$ (as required by the problem)

And we want to find the pair where A[i] + A[j] == target. Taking $n = 8$ as an example, the full search space looks like this:

Due to the constraints on $i$ and $j$, the search space is the white inverted triangle region. As you can see, the search space is $O(n^2)$ in size. A brute-force approach that checks one cell at a time would inevitably take $O(n^2)$ time. A better algorithm, however, can eliminate multiple invalid cells in a single operation, rapidly shrinking the search space to locate the solution.

Let’s see how the two-pointer solution shrinks the search space. We start by checking the top-right cell $(0, 7)$, i.e., computing A[0] + A[7]:

Suppose A[0] + A[7] is less than the target sum. Since A[7] is already the largest number, we can deduce that A[0] + A[6], A[0] + A[5], …, A[0] + A[1] are all less than the target as well. These are all invalid solutions that can be eliminated at once, as shown below. This is equivalent to eliminating all solutions where $i=0$, removing an entire row from the search space — corresponding to i++ in the two-pointer solution.

After removing a row of search space, the remaining space still forms an inverted triangle. We check the new top-right cell $(1, 7)$:

Suppose A[1] + A[7] is greater than the target sum. Now we need to eliminate all solutions where $j = 7$, removing an entire column from the search space — corresponding to j-- in the two-pointer solution:

And so on — each step removes either a row or a column from the search space. After $n$ steps, all possibilities will have been checked. The process of the search space shrinking is shown in the animation below:

Applying the Idea: 2D Matrix Search

Two Sum II might be too simple to truly require the search space concept. So let’s see how this idea applies to another problem.

Example: LeetCode 240 - Search a 2D Matrix II (Medium)

An $m \times n$ matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right
• Integers in each column are sorted in ascending order from top to bottom

Write an efficient algorithm to search for a target value in the matrix.

What’s special about this problem is that the 2D matrix itself is the search space, so we don’t need to think about the shape of the search space — we can search directly. Seeing the sorted condition, we naturally think of binary search. The midpoint for binary search would obviously be the center of the matrix:

But upon closer thought, given the matrix’s properties, this center point divides the matrix into four quadrants where only the top-left quadrant is entirely less than the center, and only the bottom-right quadrant is entirely greater. In other words, a single comparison can eliminate at most 1/4 of the search space. The bigger issue is that after removing the top-left or bottom-right quadrant, the remaining shape is no longer a regular rectangle, making it impossible to continue binary searching.

So let’s try a different approach — instead of trying to eliminate half the search space at once, we eliminate one row or one column at a time, just like in the Two Sum II problem. Following the same logic as the two-pointer solution, we can check the top-right element of the matrix: matrix[0][7].

If matrix[0][7] is less than the target, since each row is sorted, all elements in the same row must also be less than the target. This lets us eliminate an entire row.

If matrix[0][7] is greater than the target, since each column is sorted, all elements in the same column must also be greater than the target. This lets us eliminate an entire column.

So each time, we can definitely eliminate either a row or a column. After at most $\max{ \{ m, n\} }$ comparisons, we can search through the entire matrix. If you compare Two Sum II and this problem carefully, you’ll notice that even the direction in which they shrink the search space is the same.

Summary

As we can see from the examples in this article, many LeetCode problems have simple answers, but to truly internalize them and apply the ideas to new problems, you need to understand the thinking behind them. Two Sum II appears to be a simple two-pointer problem on the surface, but to come up with this approach, you need to understand the search space concept behind it.

The search space technique requires flexible application in actual problems. The 2D matrix search example in this article demonstrates a creative application of the search space idea. Here’s one more closely related problem — try to appreciate how it uses the idea of reducing the search space:

• 11. Container With Most Water