Two-Pointer Technique for Sorted Arrays

Welcome to the third module of your algorithms course! We're now moving into a new phase where we'll focus on specific, powerful algorithmic patterns. Recognizing these patterns is a key skill for efficiently solving interview problems, helping to replace guesswork with a structured thought process. This module is all about the Two Pointers and Sliding Window techniques.

Today's lesson introduces the first and most fundamental of these patterns. Your goal is to learn how to use inward-moving pointers to find a target pair in a sorted array. This technique is a classic example of how leveraging a property of the input—in this case, that it's sorted—can lead to a dramatically more efficient solution.

The Problem: Finding a Pair with a Target Sum

Let's start with a common problem: given a sorted array of integers and a target number, find two numbers in the array that add up to the target.

For example, given numbers = [2, 7, 11, 15] and target = 9, the answer is the pair (2, 7).

The most straightforward approach is to check every possible pair of numbers. You could use a nested loop: the outer loop picks the first number, and the inner loop checks it against every other number. As you know from our first module, this would result in a time complexity of $O(n^2)$. For large arrays, this is too slow and will likely result in a "Time Limit Exceeded" error in a coding platform.

The video below quickly demonstrates this brute-force approach and its performance limitations, setting the stage for a much better solution.

We can do much better. The key is to use the fact that the array is sorted.

The Two-Pointer Strategy: A Smarter Approach

Since the array is sorted, the smallest elements are at the beginning and the largest are at the end. This allows us to be much more strategic. Instead of checking pairs randomly, we can start with the two most extreme values and work our way inward.

This is the core of the inward-moving two-pointers technique.

1. Initialize a left pointer at the beginning of the array (index 0).
2. Initialize a right pointer at the end of the array (index n-1).
3. Sum the values at these two pointers: currentSum = numbers[left] + numbers[right].
4. Now, we make a decision:
   • If currentSum equals the target, we've found our pair!
   • If currentSum is less than the target, we need a larger sum. Since the array is sorted, the only way to guarantee a larger sum is to move the left pointer to the right (left++).
   • If currentSum is greater than the target, we need a smaller sum. The only way to guarantee this is to move the right pointer to the left (right--).
5. We repeat this process until the left and right pointers meet or cross, which means we've checked all possible pairs.

This logic is powerful because in each step, we definitively eliminate either the current left element or the current right element from consideration. We never need to backtrack.

The following reading provides a concise summary of this decision-making logic.

Let's visualize this process with a concrete example.

Let's trace the steps in the image above:

1. Initial state: left points to 1, right points to 6. The sum is 1 + 6 = 7.
2. Decision: Since 7 > 6 (our target), the sum is too large. We must decrease it. We move the right pointer to the left, from 6 to 4.
3. New state: left points to 1, right points to 4. The sum is 1 + 4 = 5.
4. Decision: Since 5 < 6, the sum is too small. We must increase it. We move the left pointer to the right, from 1 to 2.
5. Final state: left points to 2, right points to 4. The sum is 2 + 4 = 6.
6. Decision: The sum equals the target. We have found our pair!

The next video provides an excellent animated walkthrough of this process, which should solidify your understanding of how the pointers converge on the solution.

Implementation and Complexity Analysis

Now that you have the intuition, let's look at a full implementation in JavaScript and analyze its performance.

The following resource provides a step-by-step trace of the algorithm on a few examples, followed by a clean JavaScript implementation. It also includes a crucial analysis of the time and space complexity, which is essential knowledge for any technical interview.

To summarize the complexity:

• Time Complexity: The left pointer moves from left to right, and the right pointer moves from right to left. In each iteration of the loop, at least one pointer moves. They will eventually meet, meaning the loop runs a number of times proportional to the number of elements in the array. This gives us a linear time complexity of $O(n)$. If the input array wasn't already sorted, we would first have to sort it, making the overall time complexity $O(n\log n)$ due to the sort operation.
• Space Complexity: We only need a few variables to store the pointers and the current sum. We are not creating any new data structures that scale with the input size. This gives us a constant auxiliary space complexity of $O(1)$. This is a significant advantage over the hash map solution for the original "Two Sum" problem, which requires $O(n)$ space.

For completeness, here is one more resource that implements the entire logic, including the initial sorting step, which is necessary if the input array is not guaranteed to be sorted.

Key Takeaways

You've just learned your first major algorithmic pattern. Let's recap the core ideas:

• The inward-moving two-pointer technique is a highly efficient method for searching for pairs in a sorted array.
• The strategy works by placing one pointer at the start and another at the end, then moving them inward based on whether their sum is too small or too large.
• This approach systematically eliminates elements, guaranteeing that you check all relevant pairs in a single pass through the array.
• It achieves $O(n)$ time complexity (on a pre-sorted array) and $O(1)$ auxiliary space complexity, making it superior to both brute-force ($O(n^2)$ time) and hash-map-based solutions ($O(n)$ space).

This pattern is a foundational building block. In our next lesson, we will explore another variation where two pointers start at or near the beginning of an array and move in the same direction. This variant is ideal for a different class of problems, such as removing duplicates or processing subarrays.